Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8
9


Input: s = "cbabc"

Output: "baabc"

Explanation:

Perform the operation on the substring starting at index 0, and ending at
index 1 inclusive.

Example 2

1
2
3
4
5
6
7
8


Input: s = "aa"

Output: "az"

Explanation:

Perform the operation on the last letter.

Example 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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^5
  • s consists of lowercase English letters

Solution

Method 1 – Greedy Substring Decrement (1)

Intuition

The lexicographically smallest string can be obtained by decrementing the first contiguous substring of non-‘a’ characters from the left. This is because changing ‘a’ to ‘z’ makes the string larger, so we want to avoid that. If all characters are ‘a’, decrement the last character.

Approach

  1. Iterate from the left and find the first character that is not ‘a’.
  2. From this position, keep moving right as long as the character is not ‘a’.
  3. Decrement each of these characters by 1 (e.g., ‘b’→‘a’, ‘c’→‘b’).
  4. If all characters are ‘a’, decrement the last character to ‘z’.
  5. Return the modified string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    string smallestString(string s) {
        int n = s.size(), i = 0;
        while (i < n && s[i] == 'a') i++;
        if (i == n) {
            s[n-1] = 'z';
            return s;
        }
        while (i < n && s[i] != 'a') {
            s[i] = s[i] - 1;
            i++;
        }
        return s;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func smallestString(s string) string {
    b := []byte(s)
    i := 0
    for i < len(b) && b[i] == 'a' {
        i++
    }
    if i == len(b) {
        b[len(b)-1] = 'z'
        return string(b)
    }
    for i < len(b) && b[i] != 'a' {
        b[i]--
        i++
    }
    return string(b)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public String smallestString(String s) {
        char[] arr = s.toCharArray();
        int i = 0, n = arr.length;
        while (i < n && arr[i] == 'a') i++;
        if (i == n) {
            arr[n-1] = 'z';
            return new String(arr);
        }
        while (i < n && arr[i] != 'a') {
            arr[i]--;
            i++;
        }
        return new String(arr);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun smallestString(s: String): String {
        val arr = s.toCharArray()
        var i = 0
        while (i < arr.size && arr[i] == 'a') i++
        if (i == arr.size) {
            arr[arr.size-1] = 'z'
            return String(arr)
        }
        while (i < arr.size && arr[i] != 'a') {
            arr[i] = (arr[i] - 1).toChar()
            i++
        }
        return String(arr)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def smallestString(self, s: str) -> str:
        arr = list(s)
        i = 0
        while i < len(arr) and arr[i] == 'a':
            i += 1
        if i == len(arr):
            arr[-1] = 'z'
            return ''.join(arr)
        while i < len(arr) and arr[i] != 'a':
            arr[i] = chr(ord(arr[i]) - 1)
            i += 1
        return ''.join(arr)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn smallest_string(s: String) -> String {
        let mut arr: Vec<char> = s.chars().collect();
        let mut i = 0;
        while i < arr.len() && arr[i] == 'a' {
            i += 1;
        }
        if i == arr.len() {
            arr[arr.len()-1] = 'z';
            return arr.into_iter().collect();
        }
        while i < arr.len() && arr[i] != 'a' {
            arr[i] = ((arr[i] as u8) - 1) as char;
            i += 1;
        }
        arr.into_iter().collect()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    smallestString(s: string): string {
        let arr = s.split('');
        let i = 0;
        while (i < arr.length && arr[i] === 'a') i++;
        if (i === arr.length) {
            arr[arr.length-1] = 'z';
            return arr.join('');
        }
        while (i < arr.length && arr[i] !== 'a') {
            arr[i] = String.fromCharCode(arr[i].charCodeAt(0) - 1);
            i++;
        }
        return arr.join('');
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string. We scan the string at most twice.
  • 🧺 Space complexity: O(n), for storing the result as a character array.