Leetcode 2734: Lexicographically Smallest String After Substring Operation

Input: The input consists of a string `s` of lowercase English letters.

Example: s = 'efghi'

Constraints:

• 1 <= s.length <= 3 * 10^5

• s consists of lowercase English letters.

Output: Return the lexicographically smallest string that can be obtained after performing the operation.

Example: Output: 'defgh'

Constraints:

Goal: To find the lexicographically smallest string by selecting and performing the operation on a substring.

Steps:

• Find the first non-'a' character and perform the operation on it and all following characters.

• Stop the operation when you encounter 'a' or the end of the string.

Goal: The string `s` should contain only lowercase English letters, and its length should be within the specified range.

Steps:

• 1 <= s.length <= 3 * 10^5

• s consists of lowercase English letters.

Assumptions:

• All characters in the string are lowercase English letters.

• The string length is at least 1.

• Input: s = 'efghi'

• Explanation: The operation is performed on the first two characters 'e' and 'f', changing them to 'd' and 'e', respectively. The result is 'defgh'.

• Input: s = 'abc'

• Explanation: No operation is needed because the string is already lexicographically smallest.

• Input: s = 'bcde'

• Explanation: The operation is performed on the substring 'b' and 'c', changing 'b' to 'a'. The result is 'abde'.

Approach: The problem can be solved by iterating over the string and applying the operation on the first non-'a' characters, reducing them by 1.

Observations:

• We need to find the first character that is not 'a' and apply the operation on it.

• If the string is all 'a's, we need to change the last character to 'z'.

• Start iterating from the beginning, and when encountering the first non-'a' character, apply the operation.

Steps:

• Start from the leftmost character.

• If the character is 'a', skip it.

• When a non-'a' character is found, perform the operation to decrement it and all subsequent characters.

• If the string ends and no operation has been performed, change the last character to 'z'.

Empty Inputs:

• The string contains only 'a's.

Large Inputs:

• The string has the maximum allowed length.

Special Values:

• The string has no non-'a' characters.

Constraints:

• The input string is always non-empty.

string smallestString(string s) {
    int i = 0;
    while(i < s.size() && s[i] == 'a') i++;
    if(i >= s.size()) { s[s.size()-1] = 'z'; return s; }
    while(i < s.size() && s[i] != 'a') { s[i]--; i++; }
    return s;
}

1 : Function Definition

string smallestString(string s) {

This is the function definition of `smallestString`, which takes a string `s` as input and returns the modified string.

2 : Variable Initialization

    int i = 0;

An integer variable `i` is initialized to 0. This will be used to iterate through the string `s`.

3 : Loop - Check 'a'

    while(i < s.size() && s[i] == 'a') i++;

The function enters a while-loop to skip all the leading 'a' characters in the string by incrementing `i` until a non-'a' character is found.

4 : Condition - All 'a'

    if(i >= s.size()) { s[s.size()-1] = 'z'; return s; }

If `i` reaches the end of the string, meaning all characters were 'a', the last character is set to 'z' and the modified string `s` is returned.

5 : Loop - Decrease Non-'a'

    while(i < s.size() && s[i] != 'a') { s[i]--; i++; }

This while-loop iterates through the string starting from the first non-'a' character and decreases each character until an 'a' is encountered or the string ends.

6 : Return Statement

    return s;

After modifying the string, the function returns the modified string `s`.

Best Case: O(n) where n is the length of the string.

Average Case: O(n) because we iterate over the string once.

Worst Case: O(n) since we need to process all characters in the string.

Description: The time complexity is linear because we process each character once.

Best Case: O(1) when no operations are required.

Worst Case: O(1) since only a few variables are used.

Description: The space complexity is constant because we don't use any extra space proportional to the input size.

Leetcode 2734: Lexicographically Smallest String After Substring Operation

Explore →