🔗 2663. Lexicographically Smallest Beautiful String 2416

tags: `Weekly Contest 343` `字串(String)` `貪心(Greedy)`

題意

如果一個字串滿足以下條件，則可以稱其為 美麗的(beautiful) ：

它由英文小寫字母的前 $k$ 個字母組成。
它不包含任何長度為 $2$ 或更長的回文子字串。

給定一個長度為 $n$ 的美麗字串 $s$ 和一個正整數 $k$ 。

返回一個長度同樣為 $n$ 的美麗字串，且在所有大於 $s$ 的美麗字串中，其字典序是最小的。如果不存在這樣的字串，則返回一個空字串。

約束條件

$1 \leq n == s.length \leq 10^5$
$4 \leq k \leq 26$
$s$ 是一個美麗字串。

思路：貪心(Greedy)

由於只能使用前 $k$ 個小寫字母，因此可以將字串 $s$ 的每一個字元想像成一個 $k$ 進位制的數字。首先將字串 $s$ 轉換為數字表示，方便進行運算。這樣可以將問題轉換為一個進位運算的問題。

且根據回文字串的性質，若 $k > 2$ ，則長度為 $k$ 的回文字串必會包含一個長度為 $k-2$ 的回文字串。故在檢查一個字串沒有長度為 $2$ 或更長的回文字串，只需要考慮有沒有長度為 $2$ 和 $3$ 的回文子字串即可。

因此我們可以使用貪心(Greedy) 的方式來解決這個問題，由於要在字典序大於 $s$ 的字串中找到字典序最小的符合條件的字串，因此我們可以從字串的最後一位開始，逐步向前檢查並嘗試增加當前位的數值。如果增加後數值超過了 $k-1$ ，則將其置為 0 並向前一位進位。進位後需要檢查是否形成了回文子串，若形成則繼續增加當前位的數值。這樣循環直到找到符合條件的字串或者無法進位為止。

由於給定的字串 $s$ 是一個美麗字串，因此可以確保未被修改過的部分與其前面的字元都不會形成回文字串。

複雜度分析

時間複雜度： $O(n)$
空間複雜度： $O(n)$ ，如果能直接修改字串 $s$ 的話，空間複雜度可以降為 $O(1)$ 。

class Solution:
    def smallestBeautifulString(self, s: str, k: int) -> str:
        toInt = lambda ch: ord(ch) - ord('a')
        toChar = lambda x: chr(x + ord('a'))

        n = len(s)
        lst = list(map(toInt, s))
        i = n - 1 # 從最後一位開始
        lst[i] += 1 # 先加一

        while i < n:
            # Case 1: 需要進位
            if lst[i] == k: 
                if i == 0: # 無法進位
                    return ""
                lst[i] = 0
                lst[i - 1] += 1
                i -= 1
            # Case 2: 如果 lst[i] 和左側字元相同，或者和左側的左側字元相同，則會形成回文字串，需要繼續增加 lst[i]
            elif i and lst[i] == lst[i - 1] or i > 1 and lst[i] == lst[i - 2]:
                lst[i] += 1
            # Case 3: 若為其他情況，則根據約束條件，前面已經沒有回文字串了，重新往後檢查是否有回文字串
            else: 
                i += 1

        return ''.join(map(toChar, lst))

class Solution {
public:
    string smallestBeautifulString(string s, int k) {
        int n = s.size();
        k += 'a'; // 用 [a, k + a) 表示 [0, k) 的範圍
        int i = n - 1;
        s[i] += 1;
        while (i < n) {
            if (s[i] == k) { // 需要進位
                if (i == 0) return ""; // 無法進位
                s[i] = 'a';
                s[i - 1] += 1;
                i -= 1;
            } else if (i && s[i] == s[i - 1] || i > 1 && s[i] == s[i - 2]) { // 會形成回文字串
                s[i] += 1;
            } else { // 重新往後檢查是否有回文字串
                i += 1;
            }
        }
        return s;
    }
};