Lexicographically Smallest String After Substring Operation

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.

def smallest_string(s):
    n = len(s)
    arr = list(s)
    start = -1
    
    for i in range(n):
        if s[i] != 'a':
            start = i
            break
            
    if start == -1:
        arr[-1] = 'z'
        return "".join(arr)
    
    end = start
    while end < n and arr[end] != 'a':
        arr[end] = chr(ord(arr[end]) - 1)
        end += 1
        
    return "".join(arr)

# Example Usage
print(smallest_string("cbabc"))  # Output: "baabc"
print(smallest_string("aa"))     # Output: "az"
print(smallest_string("acbbc"))  # Output: "abaab"
print(smallest_string("leetcode")) # Output: "kddsbncd"

Explanation:

The problem requires us to find the lexicographically smallest string after performing an operation where we select a substring and decrement each character in that substring (wrapping 'a' to 'z').

1. Naive Approach:

   • Try every possible substring.
   • For each substring, decrement the characters and check if the resulting string is the smallest seen so far.
   • This would have a time complexity of O(N^3), where N is the length of the string, because generating all substrings is O(N^2) and decrementing each substring is O(N).

2. Optimal Approach:

   • The key idea is to find the first non-'a' character and decrement consecutive non-'a' characters until we encounter an 'a' or reach the end of the string.
   • If the original string contains only 'a's, then decrement the last character to 'z'.
   • This approach ensures that we create the lexicographically smallest string because we're modifying the leftmost possible substring.

Code Implementation Details:

• The code iterates through the string s to find the first character that is not 'a'.
• If no such character is found (i.e., the string contains only 'a's), it changes the last character to 'z'.
• If a non-'a' character is found, it decrements consecutive non-'a' characters until an 'a' is encountered or the string's end is reached.

Big(O) Run-time Analysis:

The optimal solution has a time complexity of O(N), where N is the length of the string s.

• The code iterates through the string at most twice: once to find the first non-'a' character and once to decrement the substring.
• Both iterations are linear with respect to the input size N.

Big(O) Space Usage Analysis:

The space complexity of the optimal solution is O(N), where N is the length of the string s.

• We convert the string s to a list arr to modify the characters in place. This list requires O(N) space.
• The other variables (e.g., start, end) take constant space O(1).

Edge Cases:

1. Empty String:
   • The problem statement specifies that the string will not be empty, so we don't need to handle this case.
2. String with Only 'a's:
   • If the string contains only 'a's, the algorithm correctly changes the last character to 'z'.
3. String with a Single Non-'a' Character:
   • If the string has only one non-'a' character, the algorithm correctly decrements that character and leaves the rest unchanged.
4. String with Non-'a' Characters at the Beginning:
   • If the string starts with non-'a' characters, the algorithm correctly decrements the consecutive non-'a' characters from the beginning.
5. String with Non-'a' Characters at the End:
   • If the string ends with non-'a' characters, the algorithm correctly decrements these characters until an 'a' is encountered or the end is reached.