3106. Lexicographically Smallest String After Operations With Constraint LeetCode Solution
In this guide, you will get 3106. Lexicographically Smallest String After Operations With Constraint LeetCode Solution with the best time and space complexity. The solution to Lexicographically Smallest String After Operations With Constraint problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Lexicographically Smallest String After Operations With Constraint
You are given a string s and an integer k.
Define a function distance(s1, s2) between two strings s1 and s2 of the same length n as:
The sum 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.
Example 1:
Input: s = “zbbz”, k = 3
Output: “aaaz”
Explanation:
Change s to “aaaz”. The distance between “zbbz” and “aaaz” is equal to k = 3.
Example 2:
Input: s = “xaxcd”, k = 4
Output: “aawcd”
Explanation:
The distance between “xaxcd” and “aawcd” is equal to k = 4.
Input: s = “lol”, k = 0
Output: “lol”
Explanation:
It’s impossible to change any character as k = 0.
Constraints:
1 <= s.length <= 100
0 <= k <= 2000
s consists only of lowercase English letters.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
3106. Lexicographically Smallest String After Operations With Constraint LeetCode Solution in C++
class Solution {
public:
string getSmallestString(string s, int k) {
string ans = s;
for (char& c : ans) {
if (k == 0)
break;
const int distToA = min(c - 'a', 'z' - c + 1);
if (k >= distToA) {
k -= distToA;
c = 'a';
} else {
// k is not enough to change the current letter to 'a', so move as
// closer to 'a' as possible.
c -= k;
k = 0;
}
}
return ans;
}
}; /* code provided by PROGIEZ */
3106. Lexicographically Smallest String After Operations With Constraint LeetCode Solution in Java
class Solution {
public String getSmallestString(String s, int k) {
StringBuilder sb = new StringBuilder(s);
for (int i = 0; i < sb.length(); ++i) {
if (k == 0)
break;
final int distToA = Math.min(sb.charAt(i) - 'a', 'z' - sb.charAt(i) + 1);
if (k >= distToA) {
k -= distToA;
sb.setCharAt(i, 'a');
} else {
// k is not enough to change the current letter to 'a', so move as
// closer to 'a' as possible.
sb.setCharAt(i, (char) (sb.charAt(i) - k));
k = 0;
}
}
return sb.toString();
}
} // code provided by PROGIEZ
3106. Lexicographically Smallest String After Operations With Constraint LeetCode Solution in Python
class Solution:
def getSmallestString(self, s: str, k: int) -> str:
ans = list(s)
for i, c in enumerate(s):
if k == 0:
break
distToA = min(ord(c) - ord('a'), ord('z') - ord(c) + 1)
if k >= distToA:
k -= distToA
ans[i] = 'a'
else:
# k is not enough to change the current letter to 'a', so move as closer
# to 'a' as possible.
ans[i] = chr(ord(c) - k)
k = 0
return ''.join(ans) # code by PROGIEZ
