2734. Lexicographically Smallest String After Substring Operation

• Time: $O(n)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  string smallestString(string s) {
    const int n = s.length();
    int 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++];

    return s;
  }
};

public class Solution {
  public String smallestString(String s) {
    char[] charArray = s.toCharArray();
    final int n = s.length();
    int i = 0;

    while (i < n && charArray[i] == 'a')
      ++i;
    if (i == n) {
      charArray[n - 1] = 'z';
      return new String(charArray);
    }

    while (i < n && charArray[i] != 'a')
      --charArray[i++];

    return new String(charArray);
  }
}

class Solution:
  def smallestString(self, s: str) -> str:
    chars = list(s)
    n = len(s)
    i = 0

    while i < n and chars[i] == 'a':
      i += 1
    if i == n:
      chars[-1] = 'z'
      return ''.join(chars)

    while i < n and s[i] != 'a':
      chars[i] = chr(ord(chars[i]) - 1)
      i += 1

    return ''.join(chars)