2734. Lexicographically Smallest String After Substring Operation

MediumGreedyString
Leetcode Link

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:

  1. Scan the string from the beginning and locate the first character that is not 'a'.
  2. Continue scanning until you reach an 'a' or the end of the string.
  3. 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.
  4. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following shows the order of node visit in a Breadth-first Search?

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:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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:].

  6. 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.

  7. 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.

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

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Example Walkthrough

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

  1. We initialize i to 0. The string s is "abcde", and we are looking for the first occurrence of a non-'a' character.

  2. 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.

  3. 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.

  4. 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.

  5. We get to the end of the string and have not found another 'a'. So, j stops at the string length (5).

  6. 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.

  7. 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.

  8. 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
Not Sure What to Study? Take the 2-min Quiz：

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫