2734. Lexicographically Smallest String After Substring Operation

MediumGreedyString

Problem Description

In the given problem, you are provided with a string s which consists only of lowercase English letters. You are allowed to perform a single operation which involves selecting a non-empty substring of s (it could be the entire string), and then replacing each character in that substring with the character that comes before it in the English alphabet. So, 'b' becomes 'a', 'c' becomes 'b', and interestingly, 'a' loops back around to become 'z'. Your task is to determine the lexicographically smallest string that can be obtained by performing this operation exactly once.

Recall that a substring is just a sequence of consecutive characters from the string, and that one string is lexicographically smaller than another if, at the first position where they differ, the character in the first string comes before the character in the second string in the alphabet.

Intuition

In solving this problem, we want to use the operation in such a way that we make the string as small as possible in lexographic order. The strategy here is to identify the first non-'a' character of the string because converting 'a' to 'z' would actually make the string lexicographically larger. When we find a non-'a' character, we want to shift it and all subsequent characters that are not 'a' so that the resulting string is lexicographically smallest.

The reason we stop at the next 'a' character after starting the shift is because changing any 'a' to a 'z' will make the string larger instead of smaller. For example, if we have the string "abc", changing it to "zbc" would make it larger lexicographically, whereas changing it to "aac" makes it smaller.

So, to break down the approach:

Scan the string from the beginning and locate the first character that is not 'a'.
Continue scanning until you reach an 'a' or the end of the string.
Replace all characters from the first non-'a' character to the character before the 'a' you've reached, by shifting them one place back in the alphabet.
If the entire string consists of 'a's, then simply change the very last character to 'z'.

This algorithm ensures that we make the minimal required changes to obtain the lexicographically smallest string possible by performing the operation exactly once.

Learn more about Greedy patterns.

Solution Approach

The solution follows a simple straight-forward approach which includes a single pass through the string and basic string manipulation operations. No complex data structures or algorithms are necessary for this implementation. The steps taken by the code can be outlined as follows:

Initialize an index variable i to 0. This variable will be used to find the position of the first non-'a' character in the string.
Use a while loop to skip any 'a's at the start of the string. The loop goes on until a non-'a' character is encountered or until we've reached the end of string. In each iteration, i is incremented by 1.
Checking if i is equal to the length of the string n. If yes, it means the string consists entirely of 'a's, so we replace the last character with 'z' and return the modified string.
If the string does not consist solely of 'a's, then initialize another variable j with the value of i and proceed to find the end of the contiguous non-'a' substring by incrementing j until an 'a' is found or the string ends.
Use string slicing to separate the string into three parts: the unchanged prefix s[:i], the modified middle [... for c in s[i:j]] where each character is shifted back in the alphabet, and the unchanged suffix s[j:].
For the middle part, a list comprehension is used along with the chr and ord functions to shift each character. The ord function gets the ASCII number for each character and then 1 is subtracted from that number because we want to replace each character by its predecessor in the English alphabet. After that, the resulting ASCII number is converted back to a character using the chr function.
Finally, the three parts of the string are concatenated and the resultant string is returned.

In summary, the solution walks through the string to find the optimal point at which to apply the operation, and then uses simple character manipulation to perform the operation and construct the resulting lexicographically smallest string.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach using the string "abcde".

We initialize i to 0. The string s is "abcde", and we are looking for the first occurrence of a non-'a' character.
We skip the first character since it's an 'a', so i becomes 1. The second character is 'b', which is not 'a', so we stop the while loop.
Since i is now 1 and not equal to the length of the string (which is 5), we know the string does not consist only of 'a's.
We then initialize j to 1 and start scanning for the next 'a'. We find that 'c', 'd', and 'e' are also not 'a', so j continues to increment.
We get to the end of the string and have not found another 'a'. So, j stops at the string length (5).
Now, we slice the string into three parts: s[:i] gives us "a", which is unchanged. We will modify s[i:j], which is "bcde". s[j:] is an empty string since j is at string end.
For each character in "bcde", we convert it to its predecessor: 'b' to 'a', 'c' to 'b', 'd' to 'c', 'e' to 'd'. This is done using ASCII values, where we subtract 1 from each character's ASCII value to get the previous character.
We then concatenate the parts together, so "a" + "abcd" + "" becomes "aabcd".

Therefore, by following the steps of the solution approach, the lexicographically smallest string we can obtain from "abcde" by performing the operation exactly once is "aabcd".

Solution Implementation

1class Solution:
2    def smallestString(self, s: str) -> str:
3        # Length of the input string
4        length_of_string = len(s)
5        # Initialize index to start from the beginning
6        index = 0
7
8        # Skip all the 'a' characters from the start
9        while index < length_of_string and s[index] == "a":
10            index += 1
11          
12        # If the string is made up entirely of 'a's, then replace the last 'a' with 'z'
13        if index == length_of_string:
14            return s[:-1] + "z"
15          
16        # Find the index where 'a' appears after the consecutive sequence of non 'a' characters
17        next_a_index = index
18        while next_a_index < length_of_string and s[next_a_index] != "a":
19            next_a_index += 1
20      
21        # Decrease every character in the substring from 'index' to 'next_a_index' by one
22        # and replace that part of the string with the new substring
23        return (s[:index] + 
24                "".join(chr(ord(char) - 1) for char in s[index:next_a_index]) +
25                s[next_a_index:])
26
27# Here's a brief explanation of how the function operates:
28# 1. The function finds the first sequence of non 'a' characters.
29# 2. It then reduces each character in this sequence by 1 lexicographically.
30# 3. If the whole string contains only 'a' characters, it turns the last 'a' into a 'z'.
31# 4. The updated string is returned as the result.
32

1class Solution {
2    public String smallestString(String s) {
3        int stringLength = s.length();
4        int firstNonAIndex = 0;
5
6        // Find the first instance of a character that is not 'a'
7        while (firstNonAIndex < stringLength && s.charAt(firstNonAIndex) == 'a') {
8            firstNonAIndex++;
9        }
10
11        // If there's no character other than 'a', replace the last 'a' with 'z'
12        if (firstNonAIndex == stringLength) {
13            return s.substring(0, stringLength - 1) + "z";
14        }
15
16        // Convert the string to a character array for manipulation
17        char[] chars = s.toCharArray();
18
19        // Start decreasing the value of characters until an 'a' is reached
20        int reduceIndex = firstNonAIndex;
21        while (reduceIndex < stringLength && chars[reduceIndex] != 'a') {
22            chars[reduceIndex] = (char) (chars[reduceIndex] - 1);
23            reduceIndex++;
24        }
25
26        // Return the new string constructed from the character array
27        return String.valueOf(chars);
28    }
29}
30

1class Solution {
2public:
3    // Function to construct the lexicographically smallest string
4    // by changing characters to 'a' or 'z' as per the conditions given
5    string smallestString(string s) {
6        int strSize = s.size(); // Get the size of the string
7        int index = 0;
8
9        // Iterate through the string and skip all 'a'
10        while (index < strSize && s[index] == 'a') {
11            ++index;
12        }
13
14        // If the string is composed of 'a' only, change the last character to 'z'
15        if (index == strSize) {
16            s[strSize - 1] = 'z'; // Changing the last character to 'z'
17            return s;
18        }
19      
20        // Iterate through the string starting from the first character that was not 'a'
21        // and decrement each character until we find 'a' or reach the end of the string
22        while (index < strSize && s[index] != 'a') {
23            s[index] = s[index] - 1; // Change character to previous one in alphabetical order
24            ++index;
25        }
26
27        // Return the modified string which should be the lexicographically smallest string possible
28        return s;
29    }
30};
31

1// Function to construct the lexicographically smallest string
2// by changing characters to 'a' or 'z' according to the conditions given
3function smallestString(s: string): string {
4    let strSize: number = s.length; // Get the length of the string
5    let index: number = 0;
6
7    // Iterate through the string and skip all 'a'
8    while (index < strSize && s[index] === 'a') {
9        ++index;
10    }
11
12    // If the string is composed of 'a' only, change the last character to 'z'
13    if (index === strSize) {
14        s = s.substring(0, strSize - 1) + 'z'; // Changing the last character to 'z'
15        return s;
16    }
17  
18    // Iterate through the string starting from the first character that was not 'a'
19    // and decrement each character until we find 'a' or reach the end of the string
20    let chars: string[] = s.split(''); // Split the string into an array of characters
21    while (index < strSize && chars[index] !== 'a') {
22        chars[index] = String.fromCharCode(chars[index].charCodeAt(0) - 1); // Change character to previous one in alphabetical order
23        ++index;
24    }
25
26    // Rejoin the array of characters into a modified string which should be the lexicographically smallest string possible
27    return chars.join('');
28}
29
30// Example usage:
31// let result: string = smallestString("abcde");
32// console.log(result); // Outputs: "abbde"
33

Time and Space Complexity

Time Complexity:

The time complexity of this code is O(n), where n is the length of the input string s.

The first while loop runs in O(n) in the worst case when all characters are "a". At best, it exits immediately if the first character is not "a".
The second while loop also runs in O(n) in the worst case, if there are no "a" characters following the first non-"a" character. At best, it exits immediately if the next character is "a".
The line with join and chr(ord(c) - 1) inside list comprehension again runs in O(n) because it iterates through the substring s[i:j]. This substring can potentially be the entire string s in the worst case.

These loops are sequential and not nested, so the time complexity remains O(n).

Space Complexity:

The space complexity of the code is also O(n).

This is because the code creates a new string with the join operation, which can potentially contain as many characters as the original string s in the worst case.
The space used to store indexes i and j is constant and does not scale with the size of the input string, therefore their contribution to space complexity is O(1).

To sum up, the space complexity of the code is dominated by the space required for the new string generated in the join operation, which is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructure

Overlapping subproblems

Non-overlapping subproblems

Constant time subproblems