1. Deciphering Strings
The developers in Hackerworld want a string processing utility based on the Ceaser cipher.
The cipher defines the distance between two characters x and y as the minimum gap between them considering
cyclic arrangement. For example, the distance between ‘a’ and ‘z’ is min(1, 25) = 1, and the distance between ‘b’
and ‘f’ is min(4, 22) = 4. For two strings of the same length, the total_distance is defined as the sum of the
distances between characters at each index i. For example, total_ distance(“ab”, “z”) = distance(‘a’, ‘z’) +
distance(‘b’, ‘c’) = 1 + 1 = 2.
Given a string s of length n, and a number k, find a string t (of length n) which is lexicographically minimum such that total_distance(s, t) s k.
Note: A string a is said to be lexicographically smaller than a string b of the same length, if a; < b;at the first index where a;!= bj.
Consider s = "bd" and k = 2.
There are several possible values of tsuch as "bb", "ce", "dd", "ac", "zd", "bf", etc. The total_distance of each of these strings with the string s does not exceed k. Amongst these, "ac" is the lexicographically minimum. Thus, the answer is "ac", without quotes.
Function Description
Complete the function getSmallestString in the editor below.
getSmallestString has the following parameters:
string s: a string of length n int k: the maximum allowed total_ distance
string: the lexicographically minimum string satisfying total_distances, t) ≤ k
Constraints
• 15ns 105
• s contains only lowercase English letters.