closestString
The distance between two strings of equal length is the number of appropriate indices where the characters in these strings differ. For example, the distance between the strings "abcde" and "bbcae" is 2.
You are given a string s. Find a new string that: has the same length, contains at most k different letters, and has the smallest possible distance from s. If there are several such strings, choose the lexicographically smallest one.
Example
- For
s = "bacbab"andk = 2, the output should beclosestString(s, k) = "baabab".
The resulting string can contain only2different letters. It’s easy to see that these letters should be'a'and'b'. Becausescontain3different letters, the distance betweensand the resulting string can’t be equal to0, but it can be equal to1as shown in example, which makes it the optimal answer.
Input/Output
-
[execution time limit] 4 seconds
-
[input] string s
A string containing only lowercase English letters. No two letters can appear the same number of times in
s.Guaranteed constraints:
3 ≤ s.length ≤ 35. -
[input] integer k
A positive integer that represents the maximum number of different characters that can be used in the resulting string.
Guaranteed constraints:
2 ≤ k ≤ 10. -
[output] string
- A new string that has the same length as
s, contains onlykdifferent letters, and has the smallest possible distance froms.
- A new string that has the same length as
Post Comment