执行子串操作后的字典序最小字符串

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

/*
题目思路：
1. 使用Java Stream API来实现相同的逻辑。
2. 我们需要找到第一个不是 'a' 的字符，并将它及其后连续的不是 'a' 的字符替换为前一个字符。
*/

import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public String smallestString(String s) {
        int n = s.length();
        int firstNonA = IntStream.range(0, n).filter(i -> s.charAt(i) != 'a').findFirst().orElse(-1);
        if (firstNonA == -1) return s;
        return IntStream.range(0, n)
                .mapToObj(i -> i >= firstNonA && s.charAt(i) != 'a' ? String.valueOf((char) (s.charAt(i) - 1)) : String.valueOf(s.charAt(i)))
                .collect(Collectors.joining());
    }
}

本题解采用贪心策略，从左到右扫描字符串。首先，如果字符串全是相同的字符且不是'a'，那么直接将整个字符串的每个字符替换为前一个字符。如果字符串中有'a'，则从第一个非'a'字符开始，将后续连续的非'a'字符都替换为前一个字符，直到遇到下一个'a'或字符串结束。这样做是因为，按照字典序，'a'是最小的字符，所以尽可能保留'a'，而将其他字符替换为前一个字符可以使得整个字符串字典序更小。

O(n)

O(1)