Lexicographically Smallest String After Substring Operation
MedPrompt
Given a string s consisting of lowercase English letters. Perform the following operation:
- Select any non-empty substring then replace every letter of the substring with the preceding letter of the English alphabet. For example, 'b' is converted to 'a', and 'a' is converted to 'z'.
Return the lexicographically smallest string after performing the operation.
Example 1:
Input: s = "cbabc"
Output: "baabc"
Explanation:
Perform the operation on the substring starting at index 0, and ending at index 1 inclusive.
Example 2:
Input: s = "aa"
Output: "az"
Explanation:
Perform the operation on the last letter.
Example 3:
Input: s = "acbbc"
Output: "abaab"
Explanation:
Perform the operation on the substring starting at index 1, and ending at index 4 inclusive.
Example 4:
Input: s = "leetcode"
Output: "kddsbncd"
Explanation:
Perform the operation on the entire string.
Constraints:
1 <= s.length <= 3 * 105sconsists of lowercase English letters
Approaches
2 approaches with complexity analysis and trade-offs.
This approach considers every possible non-empty substring of the input string s. For each substring, it performs the specified operation to generate a new candidate string. It then compares all these candidate strings to find the lexicographically smallest one.
Algorithm
- Initialize a variable
smallestStringto a value that is lexicographically larger than any possible result. - Use nested loops to iterate through all possible start indices
ifrom 0 ton-1and end indicesjfromiton-1. - For each pair
(i, j), construct a new stringtempby applying the operation on the substrings[i...j]. - To create
temp:- Take the prefix
s.substring(0, i). - Iterate
kfromitoj, transforms[k]to its predecessor (with 'a' wrapping around to 'z'), and append to a builder. - Take the suffix
s.substring(j + 1).
- Take the prefix
- Compare
tempwithsmallestString. Iftempis lexicographically smaller, updatesmallestString = temp. - After checking all substrings,
smallestStringwill hold the final answer.
Walkthrough
The core idea is to exhaustively check all possibilities. There are O(n^2) possible non-empty substrings in a string of length n. We can define each substring by its start and end indices. The algorithm proceeds as follows:
public String smallestString(String s) { int n = s.length(); String smallest = null; // Generate all possible non-empty substrings for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // Substring is from i to j inclusive char[] chars = s.toCharArray(); // Apply the operation on the substring for (int k = i; k <= j; k++) { if (chars[k] == 'a') { chars[k] = 'z'; } else { chars[k]--; } } String current = new String(chars); // Keep track of the lexicographically smallest string found so far if (smallest == null || current.compareTo(smallest) < 0) { smallest = current; } } } return smallest;}This method is too slow for the given constraints because it checks every single one of the O(n^2) substrings and for each, it builds a new string which takes O(n) time.
Complexity
Time
O(n^3). There are O(n^2) substrings. For each substring, we create a new character array (O(n)) and then a new string (O(n)), leading to O(n) work per substring. The total time is O(n^2) * O(n) = O(n^3).
Space
O(n). We need to store the character array and the resulting strings, each of which requires O(n) space.
Trade-offs
Pros
Conceptually simple and straightforward to implement.
Guaranteed to find the correct answer by checking all possibilities.
Cons
Extremely inefficient and will result in a 'Time Limit Exceeded' error for the given constraints (n up to 3 * 10^5).
A much more efficient approach is a greedy one. To make a string lexicographically smallest, we should aim to decrease the character value at the earliest possible position. The operation allows us to change a character c to c-1, which is a smaller character, unless c is 'a'. Changing 'a' to 'z' makes the character larger, which is undesirable unless it's the only option.
Algorithm
- Convert the input string
sto a character arraycharsfor modification. - Find the first index
isuch thatchars[i] != 'a'. - If no such index is found (the string is all 'a's), change the last character
chars[n-1]to 'z' and return the new string. - If an index
iis found, this is the start of our operation. Now, find the end of the segment of non-'a' characters. - Iterate with a second pointer
jstarting fromi. Whilej < nandchars[j] != 'a', decrementchars[j]and incrementj. - The loop modifies all characters in the first contiguous block of non-'a's.
- Convert the modified character array back to a string and return it.
Walkthrough
The logic is based on a key observation:
- To get the lexicographically smallest string, we must find the first character from the left that we can make smaller.
- Any character
cother than 'a' can be made smaller by changing it toc-1. - Changing 'a' to 'z' makes the string lexicographically larger at that position.
This leads to a greedy strategy:
- Iterate through the string to find the first character that is not 'a'. Let's say this is at index
start. This is the mandatory starting point for our substring operation. If we started any later, the resulting string would be lexicographically larger. - Once we start the operation at
start, we should continue it for as long as possible, as long as it doesn't make the string larger. This means we continue changing characterss[j]tos[j]-1as long ass[j]is not 'a'. We stop the operation right before the first 'a' we encounter afterstart, or at the end of the string. - If the entire string consists of 'a's, we have no choice but to change an 'a' to a 'z'. To minimize the result, we should make this change as late as possible. Therefore, we only change the last character
s[n-1]to 'z'.
This strategy can be implemented in a single pass.
public String smallestString(String s) { char[] chars = s.toCharArray(); int n = s.length(); int i = 0; // 1. Find the first non-'a' character while (i < n && chars[i] == 'a') { i++; } // 2. If all characters are 'a', change the last one to 'z' if (i == n) { chars[n - 1] = 'z'; return new String(chars); } // 3. Found a non-'a' at index i. This is our start. // Now, find the end of the non-'a' segment and modify it. int j = i; while (j < n && chars[j] != 'a') { chars[j]--; j++; } // 4. Return the modified string return new String(chars);}Complexity
Time
O(n). We iterate through the string at most twice with pointers `i` and `j`. Each character is visited a constant number of times. This is a linear time solution.
Space
O(n). In Java, strings are immutable, so we need to create a character array or a `StringBuilder` to modify the string. This requires O(n) auxiliary space.
Trade-offs
Pros
Optimal time complexity, making it very efficient for large inputs.
The logic is greedy and relatively simple to reason about.
Cons
Requires careful handling of the edge case where the string contains only 'a's.
Solutions
Solution
class Solution {public String smallestString(String s) { int n = s.length(); int i = 0; while (i < n && s.charAt(i) == 'a') { ++i; } if (i == n) { return s.substring(0, n - 1) + "z"; } int j = i; char[] cs = s.toCharArray(); while (j < n && cs[j] != 'a') { cs[j] = (char)(cs[j] - 1); ++j; } return String.valueOf(cs); }}class Solution {public: string smallestString(string s) { int n = s.size(); int i = 0; while (i < n && s[i] == 'a') { ++i; } if (i == n) { s[n - 1] = 'z'; return s; } int j = i; while (j < n && s[j] != 'a') { s[j] = s[j] - 1; ++j; } return s; }};class Solution: def smallestString(self, s: str) -> str: n = len(s) i = 0 while i < n and s[i] == "a": i += 1 if i == n: return s[: - 1] + "z" j = i while j < n and s[j] != "a": j += 1 return s[: i] + "" . join(chr(ord(c) - 1) for c in s[i: j]) + s[j:]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.