# Lexicographically Smallest String After Substring Operation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/lexicographically-smallest-string-after-substring-operation)
Canonical: https://scaleengineer.com/dsa/problems/lexicographically-smallest-string-after-substring-operation
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda), [IBM](https://scaleengineer.com/companies/ibm)
---
## 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**.

**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 * 105`
* `s` consists of lowercase English letters

# Approaches
## Brute-Force by Checking All Substrings
This approach considers every possible non-empty substring of the input string `s`. For each substring, it performs the specified operation to generate a new candidate string. It then compares all these candidate strings to find the lexicographically smallest one.
**Time:** O(n^3). There are O(n^2) substrings. For each substring, we create a new character array (O(n)) and then a new string (O(n)), leading to O(n) work per substring. The total time is O(n^2) * O(n) = O(n^3). · **Space:** O(n). We need to store the character array and the resulting strings, each of which requires O(n) space.
**Pros:** Conceptually simple and straightforward to implement.; Guaranteed to find the correct answer by checking all possibilities.
**Cons:** Extremely inefficient and will result in a 'Time Limit Exceeded' error for the given constraints (n up to 3 * 10^5).
### Explanation
The core idea is to exhaustively check all possibilities. There are O(n^2) possible non-empty substrings in a string of length n. We can define each substring by its start and end indices.
The algorithm proceeds as follows:

```java
public String smallestString(String s) {
    int n = s.length();
    String smallest = null;

    // Generate all possible non-empty substrings
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // Substring is from i to j inclusive
            char[] chars = s.toCharArray();
            
            // Apply the operation on the substring
            for (int k = i; k <= j; k++) {
                if (chars[k] == 'a') {
                    chars[k] = 'z';
                } else {
                    chars[k]--;
                }
            }
            
            String current = new String(chars);
            
            // Keep track of the lexicographically smallest string found so far
            if (smallest == null || current.compareTo(smallest) < 0) {
                smallest = current;
            }
        }
    }
    return smallest;
}
```
This method is too slow for the given constraints because it checks every single one of the O(n^2) substrings and for each, it builds a new string which takes O(n) time.
### Algorithm
- Initialize a variable `smallestString` to a value that is lexicographically larger than any possible result.
- Use nested loops to iterate through all possible start indices `i` from 0 to `n-1` and end indices `j` from `i` to `n-1`.
- For each pair `(i, j)`, construct a new string `temp` by applying the operation on the substring `s[i...j]`.
- To create `temp`:
    - Take the prefix `s.substring(0, i)`.
    - Iterate `k` from `i` to `j`, transform `s[k]` to its predecessor (with 'a' wrapping around to 'z'), and append to a builder.
    - Take the suffix `s.substring(j + 1)`.
- Compare `temp` with `smallestString`. If `temp` is lexicographically smaller, update `smallestString = temp`.
- After checking all substrings, `smallestString` will hold the final answer.

## Greedy Single-Pass Approach
A much more efficient approach is a greedy one. To make a string lexicographically smallest, we should aim to decrease the character value at the earliest possible position. The operation allows us to change a character `c` to `c-1`, which is a smaller character, unless `c` is 'a'. Changing 'a' to 'z' makes the character larger, which is undesirable unless it's the only option.
**Time:** O(n). We iterate through the string at most twice with pointers `i` and `j`. Each character is visited a constant number of times. This is a linear time solution. · **Space:** O(n). In Java, strings are immutable, so we need to create a character array or a `StringBuilder` to modify the string. This requires O(n) auxiliary space.
**Pros:** Optimal time complexity, making it very efficient for large inputs.; The logic is greedy and relatively simple to reason about.
**Cons:** Requires careful handling of the edge case where the string contains only 'a's.
### Explanation
The logic is based on a key observation:
- To get the lexicographically smallest string, we must find the *first* character from the left that we can make smaller.
- Any character `c` other than 'a' can be made smaller by changing it to `c-1`.
- Changing 'a' to 'z' makes the string lexicographically larger at that position.

This leads to a greedy strategy:
1.  Iterate through the string to find the first character that is not 'a'. Let's say this is at index `start`. This is the mandatory starting point for our substring operation. If we started any later, the resulting string would be lexicographically larger.
2.  Once we start the operation at `start`, we should continue it for as long as possible, as long as it doesn't make the string larger. This means we continue changing characters `s[j]` to `s[j]-1` as long as `s[j]` is not 'a'. We stop the operation right before the first 'a' we encounter after `start`, or at the end of the string.
3.  If the entire string consists of 'a's, we have no choice but to change an 'a' to a 'z'. To minimize the result, we should make this change as late as possible. Therefore, we only change the last character `s[n-1]` to 'z'.

This strategy can be implemented in a single pass.

```java
public String smallestString(String s) {
    char[] chars = s.toCharArray();
    int n = s.length();
    int i = 0;

    // 1. Find the first non-'a' character
    while (i < n && chars[i] == 'a') {
        i++;
    }

    // 2. If all characters are 'a', change the last one to 'z'
    if (i == n) {
        chars[n - 1] = 'z';
        return new String(chars);
    }

    // 3. Found a non-'a' at index i. This is our start.
    //    Now, find the end of the non-'a' segment and modify it.
    int j = i;
    while (j < n && chars[j] != 'a') {
        chars[j]--;
        j++;
    }

    // 4. Return the modified string
    return new String(chars);
}
```
### Algorithm
- Convert the input string `s` to a character array `chars` for modification.
- Find the first index `i` such that `chars[i] != 'a'`.
- If no such index is found (the string is all 'a's), change the last character `chars[n-1]` to 'z' and return the new string.
- If an index `i` is found, this is the start of our operation. Now, find the end of the segment of non-'a' characters.
- Iterate with a second pointer `j` starting from `i`. While `j < n` and `chars[j] != 'a'`, decrement `chars[j]` and increment `j`.
- The loop modifies all characters in the first contiguous block of non-'a's.
- Convert the modified character array back to a string and return it.

# Solutions
### Java

```java
class Solution {
public
  String smallestString(String s) {
    int n = s.length();
    int i = 0;
    while (i < n && s.charAt(i) == 'a') {
      ++i;
    }
    if (i == n) {
      return s.substring(0, n - 1) + "z";
    }
    int j = i;
    char[] cs = s.toCharArray();
    while (j < n && cs[j] != 'a') {
      cs[j] = (char)(cs[j] - 1);
      ++j;
    }
    return String.valueOf(cs);
  }
}

```

### CPP

```cpp
class Solution {
public:
  string smallestString(string s) {
    int n = s.size();
    int i = 0;
    while (i < n && s[i] == 'a') {
      ++i;
    }
    if (i == n) {
      s[n - 1] = 'z';
      return s;
    }
    int j = i;
    while (j < n && s[j] != 'a') {
      s[j] = s[j] - 1;
      ++j;
    }
    return s;
  }
};

```

### Python

```python
class Solution:
    def smallestString(self, s: str) -> str: n = len(s) i = 0 while i < n and s[i] == "a": i += 1 if i == n: return s[: - 1] + "z" j = i while j < n and s[j] != "a": j += 1 return s[: i] + "" . join(chr(ord(c) - 1) for c in s[i: j]) + s[j:]

```