Question

2734. Lexicographically Smallest String After Substring Operation

中文文档

Description

You are given a string s consisting of only lowercase English letters. In one operation, you can do the following:

• Select any non-empty substring of s, possibly the entire string, then replace each one of its characters with the previous character of the English alphabet. For example, 'b' is converted to 'a', and 'a' is converted to 'z'.

Return _the lexicographically smallest string you can obtain after performing the above operation exactly once._

A substring is a contiguous sequence of characters in a string.

A string x is lexicographically smaller than a string y of the same length if x[i] comes before y[i] in alphabetic order for the first position i such that x[i] != y[i].

 

Example 1:

Input: s = "cbabc"
Output: "baabc"
Explanation: We apply the operation on the substring starting at index 0, and ending at index 1 inclusive. 
It can be proven that the resulting string is the lexicographically smallest. 

Example 2:

Input: s = "acbbc"
Output: "abaab"
Explanation: We apply the operation on the substring starting at index 1, and ending at index 4 inclusive. 
It can be proven that the resulting string is the lexicographically smallest. 

Example 3:

Input: s = "leetcode"
Output: "kddsbncd"
Explanation: We apply the operation on the entire string. 
It can be proven that the resulting string is the lexicographically smallest. 

 

Constraints:

• 1 <= s.length <= 3 * 105
• s consists of lowercase English letters

Solutions

Solution 1

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:]

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);
  }
}

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;
  }
};

func smallestString(s string) string {
  n := len(s)
  i := 0
  for i < n && s[i] == 'a' {
    i++
  }
  cs := []byte(s)
  if i == n {
    cs[n-1] = 'z'
    return string(cs)
  }
  j := i
  for j < n && cs[j] != 'a' {
    cs[j] = cs[j] - 1
    j++
  }
  return string(cs)
}

function smallestString(s: string): string {
  const cs: string[] = s.split('');
  const n: number = cs.length;
  let i: number = 0;
  while (i < n && cs[i] === 'a') {
    i++;
  }

  if (i === n) {
    cs[n - 1] = 'z';
    return cs.join('');
  }

  let j: number = i;
  while (j < n && cs[j] !== 'a') {
    const c: number = cs[j].charCodeAt(0);
    cs[j] = String.fromCharCode(c - 1);
    j++;
  }

  return cs.join('');
}

impl Solution {
  pub fn smallest_string(s: String) -> String {
    let mut cs: Vec<char> = s.chars().collect();
    let n = cs.len();
    let mut i = 0;

    while i < n && cs[i] == 'a' {
      i += 1;
    }

    if i == n {
      cs[n - 1] = 'z';
      return cs.into_iter().collect();
    }

    let mut j = i;
    while j < n && cs[j] != 'a' {
      cs[j] = ((cs[j] as u8) - 1) as char;
      j += 1;
    }

    cs.into_iter().collect()
  }
}