Define a function distance(s1, s2) between two strings s1 and s2 of the same length n as:
Thesum of the minimum distance between s1[i] and s2[i] when the characters from 'a' to 'z' are placed in a cyclic order, for all i in the range [0, n - 1].
For example, distance("ab", "cd") == 4, and distance("a", "z") == 1.
You can change any letter of s to any other lowercase English letter, any number of times.
Return a string denoting the lexicographically smallest string t you can get after some changes, such that distance(s, t) <= k.
To get the lexicographically smallest string t such that the cyclic distance between s and t is at most k, we should try to make each character of t as small as possible, using up the available k budget greedily from left to right.
classSolution {
public: string getSmallestString(string s, int k) {
string t = s;
for (int i =0; i < s.size(); ++i) {
for (char c ='a'; c <='z'; ++c) {
int d = abs(s[i]-c);
d = min(d, 26-d);
if (d <= k) {
t[i] = c;
k -= d;
break;
}
}
}
return t;
}
};
classSolution {
public String getSmallestString(String s, int k) {
char[] arr = s.toCharArray();
for (int i = 0; i < arr.length; i++) {
for (char c ='a'; c <='z'; c++) {
int d = Math.abs(arr[i]-c);
d = Math.min(d, 26-d);
if (d <= k) {
arr[i]= c;
k -= d;
break;
}
}
}
returnnew String(arr);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution {
fungetSmallestString(s: String, k: Int): String {
val arr = s.toCharArray()
var rem = k
for (i in arr.indices) {
for (c in'a'..'z') {
var d = Math.abs(arr[i]-c)
d = minOf(d, 26-d)
if (d <= rem) {
arr[i] = c
rem -= d
break }
}
}
return String(arr)
}
}
1
2
3
4
5
6
7
8
9
10
11
12
classSolution:
defgetSmallestString(self, s: str, k: int) -> str:
ans = []
for ch in s:
for c in map(chr, range(ord('a'), ord('z')+1)):
d = abs(ord(ch)-ord(c))
d = min(d, 26-d)
if d <= k:
ans.append(c)
k -= d
breakreturn''.join(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
impl Solution {
pubfnget_smallest_string(s: String, mut k: i32) -> String {
letmut arr: Vec<u8>= s.bytes().collect();
for i in0..arr.len() {
for c inb'a'..=b'z' {
letmut d = (arr[i] asi32- c asi32).abs();
d = d.min(26-d);
if d <= k {
arr[i] = c;
k -= d;
break;
}
}
}
String::from_utf8(arr).unwrap()
}
}