LeetCode 2734 - Lexicographically Smallest String After Substring Operation
The problem gives us a lowercase English string s. We must perform exactly one operation: 1. Choose any non-empty substring. 2. Replace every character in that substring with the previous character in the alphabet.
Difficulty: 🟡 Medium
Topics: String, Greedy
Solution
Problem Understanding
The problem gives us a lowercase English string s. We must perform exactly one operation:
- Choose any non-empty substring.
- Replace every character in that substring with the previous character in the alphabet.
'b'becomes'a''c'becomes'b''a'wraps around and becomes'z'
After performing exactly one such operation, we must return the lexicographically smallest possible resulting string.
Lexicographical order works like dictionary order. When comparing two strings, the first position where they differ determines which string is smaller. A smaller character earlier in the string is always more important than any later characters.
For example:
"abc"is smaller than"abd"because'c' < 'd'"aac"is smaller than"aba"because the second character'a' < 'b'
The constraints are important:
1 <= s.length <= 3 * 10^5
This means the input can be very large, so any solution worse than linear or near-linear time will likely be too slow. A brute-force solution that tries every substring would be infeasible.
There are several important edge cases:
- A string consisting entirely of
'a'characters. - A string where the first non-
'a'appears late in the string. - A single-character string.
- Strings where changing a longer substring may accidentally introduce
'z'characters from'a', making the result worse. - Cases where the optimal substring is the entire suffix of consecutive non-
'a'characters.
The most important observation is that converting 'a' into 'z' is harmful for lexicographical order unless we are forced to do it because every character is already 'a'.
Approaches
Brute Force Approach
A straightforward solution is to try every possible non-empty substring.
For each substring:
- Create a copy of the string.
- Decrement every character in the chosen substring.
- Compare the resulting string with the current best answer.
- Keep the lexicographically smallest result.
This works because it exhaustively checks every legal operation.
However, the number of substrings in a string of length n is:
$$\frac{n(n+1)}{2}$$
For each substring, modifying and comparing strings costs O(n) time.
Therefore, the total complexity becomes O(n^3) in the worst case, which is far too slow for n = 3 * 10^5.
Optimal Greedy Approach
The key insight is that lexicographical order is dominated by earlier characters.
If we can make an earlier character smaller, that is almost always beneficial.
Decreasing any non-'a' character improves the string because:
'b' -> 'a''c' -> 'b'- etc.
But decreasing 'a' creates 'z', which makes the string much larger.
Therefore:
- We should skip leading
'a'characters. - Once we find the first character that is not
'a', we should decrement as many consecutive non-'a'characters as possible. - We stop once we encounter another
'a'.
Why is this optimal?
Because decreasing earlier characters gives the maximum lexicographical benefit, and continuing through consecutive non-'a' characters keeps improving the string without introducing harmful 'z' characters.
If the entire string consists only of 'a', we are forced to change some substring. In that case, the best choice is to change only the last character:
"aa"becomes"az"
Changing any earlier 'a' would place a 'z' earlier in the string, producing a worse result.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n³) | O(n) | Tries every substring and constructs every result |
| Optimal | O(n) | O(n) | Greedily decrements the first maximal block of non-'a' characters |
Algorithm Walkthrough
- Convert the string into a mutable character array.
Strings are immutable in Python and Go, so using a mutable structure makes in-place updates easier.
2. Scan from left to right until finding the first character that is not 'a'.
Leading 'a' characters should not be modified because they would become 'z', making the string lexicographically larger.
3. If every character is 'a', decrement only the last character.
Since we must perform exactly one operation, at least one character must change. Converting the final 'a' into 'z' minimizes the damage because the change occurs as late as possible.
4. Otherwise, start from the first non-'a' character and continue while characters are not 'a'.
For each character:
- Replace it with its previous alphabet character.
- Stop once another
'a'is encountered.
Continuing further would convert 'a' into 'z', which is harmful.
6. Return the modified string.
Why it works
The algorithm relies on the fact that lexicographical order depends primarily on earlier positions. The first opportunity to decrease a character should always be taken. Once a non-'a' block begins, decreasing every character in that block continues improving the string. Stopping before an 'a' prevents introducing a 'z', which would worsen the result. If no non-'a' character exists, modifying only the last character minimizes the unavoidable negative impact.
Python Solution
class Solution:
def smallestString(self, s: str) -> str:
chars = list(s)
n = len(chars)
index = 0
# Skip leading 'a' characters
while index < n and chars[index] == 'a':
index += 1
# Entire string is all 'a'
if index == n:
chars[-1] = 'z'
return "".join(chars)
# Decrement consecutive non-'a' characters
while index < n and chars[index] != 'a':
chars[index] = chr(ord(chars[index]) - 1)
index += 1
return "".join(chars)
The implementation begins by converting the string into a list of characters so modifications can be performed efficiently.
The first loop skips all leading 'a' characters. These characters are intentionally ignored because changing them would produce 'z', which is lexicographically worse.
If the scan reaches the end of the string, then every character was 'a'. Since the operation is mandatory, the code changes only the final character to 'z'.
Otherwise, the second loop decrements every consecutive non-'a' character starting from the first eligible position. The loop stops immediately when another 'a' is encountered because further changes would introduce unwanted 'z' characters.
Finally, the character list is joined back into a string and returned.
Go Solution
func smallestString(s string) string {
chars := []byte(s)
n := len(chars)
index := 0
// Skip leading 'a'
for index < n && chars[index] == 'a' {
index++
}
// Entire string is all 'a'
if index == n {
chars[n-1] = 'z'
return string(chars)
}
// Decrement consecutive non-'a'
for index < n && chars[index] != 'a' {
chars[index]--
index++
}
return string(chars)
}
The Go implementation follows the same logic as the Python solution.
Instead of converting to a list, Go converts the string into a []byte slice because strings are immutable. Since lowercase English letters are ASCII characters, decrementing bytes directly is safe and efficient.
There are no integer overflow concerns because character values remain within lowercase alphabet ranges.
Worked Examples
Example 1
Input:
s = "cbabc"
Initial characters:
| Index | Character |
|---|---|
| 0 | c |
| 1 | b |
| 2 | a |
| 3 | b |
| 4 | c |
We scan for the first non-'a'.
- Index 0 is
'c', stop scanning.
Now decrement consecutive non-'a' characters:
| Index | Before | After |
|---|---|---|
| 0 | c | b |
| 1 | b | a |
At index 2 we encounter 'a', so we stop.
Final string:
"baabc"
Example 2
Input:
s = "aa"
Scan for first non-'a':
| Index | Character |
|---|---|
| 0 | a |
| 1 | a |
All characters are 'a'.
We must perform one operation, so change only the last character:
| Index | Before | After |
|---|---|---|
| 1 | a | z |
Final string:
"az"
Example 3
Input:
s = "acbbc"
Scan for first non-'a':
| Index | Character |
|---|---|
| 0 | a |
| 1 | c |
Start decrementing from index 1:
| Index | Before | After |
|---|---|---|
| 1 | c | b |
| 2 | b | a |
| 3 | b | a |
| 4 | c | b |
No 'a' interrupts the sequence.
Final string:
"abaab"
Example 4
Input:
s = "leetcode"
First character is already non-'a'.
Decrement every character:
| Before | After |
|---|---|
| l | k |
| e | d |
| e | d |
| t | s |
| c | b |
| o | n |
| d | c |
| e | d |
Final string:
"kddsbncd"
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each character is visited at most once |
| Space | O(n) | Mutable character storage requires linear space |
The algorithm performs a single left-to-right scan. Even though there are two loops, each character is processed at most once overall, so the runtime is linear.
The extra space comes from creating a mutable copy of the string. In Python this is the character list, and in Go it is the byte slice.
Test Cases
sol = Solution()
assert sol.smallestString("cbabc") == "baabc" # basic mixed example
assert sol.smallestString("aa") == "az" # all 'a' characters
assert sol.smallestString("acbbc") == "abaab" # decrement long suffix
assert sol.smallestString("leetcode") == "kddsbncd" # decrement entire string
assert sol.smallestString("a") == "z" # single character edge case
assert sol.smallestString("b") == "a" # single non-'a' character
assert sol.smallestString("ab") == "aa" # skip leading 'a'
assert sol.smallestString("ba") == "aa" # stop before trailing 'a'
assert sol.smallestString("aaaabc") == "aaaabb" # first non-'a' late in string
assert sol.smallestString("abcde") == "aabcd" # decrement maximal segment
assert sol.smallestString("aaaaa") == "aaaaz" # all 'a' longer string
assert sol.smallestString("caaa") == "baaa" # decrement only first character
assert sol.smallestString("aaabaaa") == "aaaaaaa" # middle block
assert sol.smallestString("bbbb") == "aaaa" # decrement entire string
| Test | Why |
|---|---|
"cbabc" |
Standard mixed example |
"aa" |
All characters are 'a' |
"acbbc" |
Long consecutive non-'a' block |
"leetcode" |
Entire string should be modified |
"a" |
Smallest possible input |
"b" |
Single non-'a' character |
"ab" |
Leading 'a' should be skipped |
"ba" |
Stop when encountering 'a' |
"aaaabc" |
First modifiable character appears late |
"abcde" |
Continuous decrement across string |
"aaaaa" |
All 'a' with larger length |
"caaa" |
Only one character should change |
"aaabaaa" |
Internal non-'a' block |
"bbbb" |
Entire string transformed |
Edge Cases
One important edge case is when the entire string consists only of 'a' characters. This is tricky because decrementing 'a' produces 'z', which makes the string lexicographically larger. However, the operation is mandatory, so at least one character must change. The optimal strategy is to modify only the last character, ensuring the harmful 'z' appears as late as possible.
Another important case is when the string begins with several 'a' characters before reaching a non-'a' character. A naive implementation might start decrementing immediately, turning leading 'a' characters into 'z'. That would produce a much larger string. The algorithm correctly skips all leading 'a' characters before beginning modifications.
A third critical edge case occurs when a sequence of non-'a' characters is interrupted by an 'a'. The optimal substring must stop before that 'a'. Continuing further would convert the 'a' into 'z', which outweighs any benefit gained from later character reductions. The implementation explicitly terminates the decrement loop once an 'a' is encountered.