Lexicographically Smallest String After Substring Operation

Medium

Asked by:

69 views

Topics:

Greedy AlgorithmsStrings

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 * 10⁵
s consists of lowercase English letters

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `s`?
Can the input string `s` be empty or null?
If there are multiple substrings that lead to the lexicographically smallest string, can I return any one of them?
Is it guaranteed that the input string `s` only contains lowercase English letters?
By 'substring', do you mean a contiguous sequence of characters within the string `s`?

Brute Force Solution

Approach

The brute force strategy tries every possible substring within the original string and changes all of its characters to 'a'. Then, it compares all these resulting strings to find the smallest one in dictionary order. It's like trying out every possible combination to see which one is the best.

Here's how the algorithm would work step-by-step:

Start by considering the very first character of the string.
Imagine that the substring starts and ends at that first character. Change that character to 'a', and keep the new string.
Now, imagine the substring starts at the first character, but ends at the second character. Change both characters to 'a', and keep the new string.
Continue extending the substring, changing more and more characters to 'a' until the substring ends at the last character of the original string. Keep each of these new strings.
Next, move to the second character of the original string and repeat the process. Imagine a substring starting and ending at the second character, changing it to 'a'. Keep the new string.
Again, extend the substring from the second character to the third, then the fourth, and so on, changing all characters in the substring to 'a' and keeping each new string.
Keep repeating this process, moving the starting position of the substring along the entire string, until you've tried every possible substring.
Finally, compare all the 'a'-modified strings that you've created. The one that comes first alphabetically is the lexicographically smallest string.

Code Implementation

def find_smallest_string(original_string):
    smallest_string = original_string
    string_length = len(original_string)

    for start_index in range(string_length):
        for end_index in range(start_index, string_length):
            # Create a list of characters from the string
            modified_string_list = list(original_string)

            # Change the substring to 'a' characters
            for index in range(start_index, end_index + 1):
                modified_string_list[index] = 'a'

            # Join the list of chars back to string
            modified_string = "".join(modified_string_list)

            # Check if new string is smaller.
            if modified_string < smallest_string:

                smallest_string = modified_string

    return smallest_string

Big(O) Analysis

Time Complexity

O(n³) – The algorithm iterates through all possible substrings of the input string of length n. There are O(n²) possible substrings because we consider each starting position and then extend the substring to each possible ending position. For each substring, the algorithm replaces the characters within that substring with 'a', which takes O(n) time in the worst case where the substring is the entire string. Therefore, the overall time complexity is O(n² * n) = O(n³).

Space Complexity

O(N^2) – The algorithm generates all possible substrings by iterating through the input string of length N, resulting in approximately N^2 substrings. For each substring, a new string of length N is created, modified, and stored for comparison. The algorithm maintains a collection of these N^2 strings. Therefore, the auxiliary space required to store all these strings grows quadratically with the input size N, leading to a space complexity of O(N^2).

Optimal Solution

Approach

The goal is to find the smallest possible string by changing a single substring. We can do this efficiently by focusing on making the first differing character as small as possible. We want to find the first character that's not 'a' and change the substring starting there to 'a's until we reach the end or another 'a'.

Here's how the algorithm would work step-by-step:

Go through the string character by character, starting from the beginning.
Look for the very first character that isn't an 'a'.
Once you find it, start changing characters to 'a's from that position.
Keep changing to 'a's until you either reach the end of the string or encounter another 'a'.
That's it! You've created the lexicographically smallest string possible with a single substring operation.

Code Implementation

def find_smallest_string(input_string):
    string_list = list(input_string)
    string_length = len(input_string)
    start_index = -1

    # Find the first non-'a' character.
    for index in range(string_length):
        if string_list[index] != 'a':
            start_index = index
            break

    # If all chars are 'a', no change needed.
    if start_index == -1:
        return input_string

    # Modify the substring to 'a's.
    for index in range(start_index, string_length):
        # Stop if we encounter another 'a'.
        if string_list[index] == 'a':
            break

        string_list[index] = 'a'

    return "".join(string_list)

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string of length n at most once to find the first non-'a' character. After locating the first non-'a', it iterates through another substring to convert characters to 'a' until it reaches the end or encounters another 'a'. Therefore, the dominant operation involves iterating through the string once, making the time complexity O(n).

Space Complexity

O(1) – The algorithm modifies the input string in-place. It doesn't use any additional data structures such as arrays, lists, or hash maps that scale with the input size N (the length of the string). Therefore, the auxiliary space required remains constant irrespective of the input string's length.

Edge Cases

Case	How to Handle
Empty or null input string	Return an empty string if the input is null or empty, as there's nothing to modify.
String of length 1	If the string length is 1, apply the operation to the single character if possible, wrapping 'a' to 'z'; otherwise, return the original string.
String containing only 'a' characters	Apply the operation to the entire string to convert all 'a's to 'z's.
String already lexicographically smallest (e.g., 'aaaa')	If already smallest, convert all a's to z's in the minimal substring.
Long string with a small modifiable substring near the end.	The algorithm should correctly identify and modify the substring starting as late as possible to achieve the smallest lexicographical order.
String starts with 'a', but has other modifiable characters later.	Skip leading 'a's and start the substring operation at the first character that can be decremented without wrapping to 'z'.
Large input string to test for time complexity	The solution should iterate through the string at most once to find the optimal substring, resulting in O(n) time complexity.
No valid substring found (string contains no chars > 'a')	The algorithm finds the minimum substring of contiguous characters greater than 'a', or applies to the entire string of 'a's if none are found.

Empty or null input string

How to Handle:

Return an empty string if the input is null or empty, as there's nothing to modify.

String of length 1

How to Handle:

If the string length is 1, apply the operation to the single character if possible, wrapping 'a' to 'z'; otherwise, return the original string.

String containing only 'a' characters

How to Handle:

Apply the operation to the entire string to convert all 'a's to 'z's.

String already lexicographically smallest (e.g., 'aaaa')

How to Handle:

If already smallest, convert all a's to z's in the minimal substring.

Long string with a small modifiable substring near the end.

How to Handle:

The algorithm should correctly identify and modify the substring starting as late as possible to achieve the smallest lexicographical order.

String starts with 'a', but has other modifiable characters later.

How to Handle:

Skip leading 'a's and start the substring operation at the first character that can be decremented without wrapping to 'z'.

Large input string to test for time complexity

How to Handle:

The solution should iterate through the string at most once to find the optimal substring, resulting in O(n) time complexity.

No valid substring found (string contains no chars > 'a')

How to Handle:

The algorithm finds the minimum substring of contiguous characters greater than 'a', or applies to the entire string of 'a's if none are found.