Lexicographically Smallest String After Substring Operation Solution
Lexicographically Smallest String After Substring Operation solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Lexicographically Smallest String After Substring Operation is a medium coding problem on strings and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a lowercase string s. Perform the following operation exactly once: choose a non-empty substring of s and replace every letter in it by the previous letter of the alphabet, where 'a' becomes 'z'.
Return the lexicographically smallest string you can obtain.
Example 1
Input: s = "kairo"
Output: jairo
Explanation: Shift just the `k`; extending the substring onto the `a` would turn it into `z`.
Example 2
Input: s = "abba"
Output: aaaa
Explanation: Shift the substring `"bb"`.
Example 3
Input: s = "aaa"
Output: aaz
Explanation: Some letter must change, and an `a` can only become `z`; changing the last one costs the least.
Constraints
1 <= s.length <= 3 * 10^5s consists of lowercase English letters
Hints for Lexicographically Smallest String After Substring Operation
Hint 1
Shifting any letter other than
amakes it smaller; shifting anamakes it much larger.Hint 2
Leading
as are already as small as possible — leave them. Start at the first letter that is nota.Hint 3
From there, shift every letter up to (not including) the next
a. If the string is allas, you are forced to turn the last one intoz.
How to solve Lexicographically Smallest String After Substring Operation
Decrease the first maximal block of non-a letters. Everything before it is already optimal, and stopping before the next a avoids turning it into z.
Approach
- Find the first index
iwiths[i] != 'a'. - If there is none, change the last character to
'z'and return. - Otherwise, starting at
i, replace each letter with its predecessor while the letter is not'a'; stop at the first'a'or at the end.
Why it works
The leading as cannot get smaller, and touching any of them makes that position a z, so the earliest position we can improve is the first non-a; improving it beats every string that leaves it alone. Continuing over further non-a letters only makes more positions smaller, while including an a would make that position larger, so the block stops right before the next a. When the string is all as some letter must become z, and putting it at the last position keeps the longest possible prefix of as.
Complexity
- Time —
O(n) - Space —
O(n) for the output
Pitfalls
- The operation is mandatory — an all-
astring cannot stay unchanged. - Do not continue past an
a: it would wrap around toz. - Only one substring may be chosen, so only the first non-
ablock changes.
Reference solution
Python
def smallestString(s: str) -> str:
a = list(s)
n = len(a)
i = 0
while i < n and a[i] == "a":
i += 1
if i == n:
a[-1] = "z"
return "".join(a)
while i < n and a[i] != "a":
a[i] = chr(ord(a[i]) - 1)
i += 1
return "".join(a)Java
public static String smallestString(String s) {
char[] a = s.toCharArray();
int n = a.length, i = 0;
while (i < n && a[i] == 'a') i++;
if (i == n) {
a[n - 1] = 'z';
return new String(a);
}
while (i < n && a[i] != 'a') {
a[i]--;
i++;
}
return new String(a);
}C++
string smallestString(string s) {
int n = s.size(), i = 0;
while (i < n && s[i] == 'a') i++;
if (i == n) {
s[n - 1] = 'z';
return s;
}
while (i < n && s[i] != 'a') {
s[i]--;
i++;
}
return s;
}JavaScript
var smallestString = function(s) {
var a = s.split(""), n = a.length, i = 0;
while (i < n && a[i] === "a") i++;
if (i === n) {
a[n - 1] = "z";
return a.join("");
}
while (i < n && a[i] !== "a") {
a[i] = String.fromCharCode(a[i].charCodeAt(0) - 1);
i++;
}
return a.join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms