Lexicographically Smallest String After Substring Operation

Medium

Amazon

5 views

Topics:

StringsGreedy Algorithms

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

Lexicographically Smallest String After Substring Operation

Medium

Amazon

5 views

Topics:

StringsGreedy Algorithms

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

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 characters are allowed in the input string? Is it only lowercase English letters, or could it include uppercase letters, numbers, or special characters?
Can the input string be empty or null?
If there are multiple substrings that, when replaced with the lexicographically smallest character, result in the same overall lexicographically smallest string, should I return the result from the first such substring, or is any of them acceptable?
What is the maximum length of the input string?
Are there any constraints on the memory usage of my solution?

Brute Force Solution

Approach

The brute force approach to this problem involves trying every possible substring operation on the given string. We will generate all possible modified strings and compare them to find the lexicographically smallest one. It's like testing every single possibility, no matter how inefficient, to guarantee we find the absolute best result.

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

Consider every possible section (substring) of the given string.
For each of these sections, create a new string where all the characters in that section are changed to 'a'.
Compare each of these newly created strings with each other.
Also, compare each of the newly created strings to the original string.
Keep track of the string that comes first alphabetically (lexicographically smallest).
After checking all sections and comparing all strings, the one you kept track of is the lexicographically smallest string after a substring operation.

Code Implementation

def find_lexicographically_smallest_string_after_substring_operation(input_string):
    smallest_string = input_string
    string_length = len(input_string)

    for start_index in range(string_length):
        for end_index in range(start_index, string_length):

            #Create the modified string with 'a's in the substring
            modified_string = list(input_string)

            for index in range(start_index, end_index + 1):
                modified_string[index] = 'a'
            modified_string = "".join(modified_string)

            # Compare the modified string to the current smallest
            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. The outer loop considers the starting position of the substring (n possibilities), and the inner loop considers the ending position of the substring (up to n possibilities). This gives us O(n²) substrings. For each substring, we create a new string by replacing the substring with 'a's, which takes O(n) time. Finally, we compare these generated strings (at most O(n²) of them) to find the lexicographically smallest, which requires comparing strings of length n. Thus, the overall time complexity is O(n²) * O(n), which simplifies to O(n³).

Space Complexity

O(N^2) – The brute force algorithm generates all possible substrings of the input string. In the worst-case scenario, where N is the length of the input string, there can be O(N^2) substrings. For each substring, a modified string is created, leading to O(N^2) strings being stored. Each string requires O(N) space in the worst case; therefore, the total auxiliary space needed to store all modified strings can reach O(N^2 * N) which we simplify to O(N^2) as we compare to the original input string of length N. The algorithm keeps track of the lexicographically smallest string found so far, which takes O(N) space; this is dominated by the space used to store all the substring modifications and hence does not change the overall space complexity.

Optimal Solution

Approach

To find the lexicographically smallest string, we need to find the earliest position where we can make a change that results in a smaller letter. We'll look for the first occurrence of a character that can be decremented to a smaller, valid character, and apply that change.

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

Start from the beginning of the string.
Look for the first character that is not 'a'.
If you find such a character, start a substring at that position.
Keep going in the substring as long as the characters can be decremented and still remain greater than or equal to 'a'.
Decrement each character in that substring by one (change 'b' to 'a', 'c' to 'b', etc.).
Stop when you reach a character that can't be decremented while staying greater than or equal to 'a', or you reach the end of the string.
The modified string will be the lexicographically smallest possible result.

Code Implementation

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

    # Find the starting index for the substring operation
    for index in range(string_length):
        if string_list[index] != 'a':
            start_index = index
            break

    # If no such index found, no operation needed
    if start_index == -1:
        return input_string

    # Decrement characters until 'a' is reached or end is hit
    for index in range(start_index, string_length):
        character_value = ord(string_list[index])
        if character_value > ord('a'):
            string_list[index] = chr(character_value - 1)
        else:
            break

    return "".join(string_list)

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string of length n at most twice. The first iteration searches for the first character that is not 'a'. The second iteration (if a non-'a' character is found) modifies a substring until an 'a' is encountered or the end of the string is reached. In the worst case, the algorithm modifies the entire string once after finding the initial non-'a' character. Therefore, the time complexity is linearly proportional to the size of the input string, resulting in O(n).

Space Complexity

O(N) – The provided solution requires creating a new string or modifying the existing string in place. Although the plain English explanation doesn't explicitly state creation of a new string, the modification step inherently requires temporary storage when strings are immutable in some languages. The space needed is proportional to the length of the input string, where N represents the length of the input string. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input string	Return an empty string as there's nothing to modify.
String with only one character	Since no substring operation is possible with a single character, return the original string.
String already lexicographically smallest (e.g., 'aaaa')	If no character can be decremented to produce a smaller string, return the original string.
String with only 'a' characters except the last one	Decrement the last non-'a' character to obtain the lexicographically smallest string.
String contains characters beyond 'a'-'z'	Handle characters outside the range 'a' to 'z' appropriately (e.g., ignore or throw an exception), depending on problem specifications.
Large input string (performance implications)	The solution should iterate through the string at most once for linear time complexity, avoiding performance issues with large strings.
String starts with 'a'	Start checking from the second character and modify the first non 'a' character from the left.
String with leading or trailing spaces	The problem statement does not mention it, so assume there are no leading or trailing spaces, or handle them by trimming the input string.