LeetCode 3398. Smallest Substring With Identical Characters I

December 22, 2024

weekly contest 429。
Q3 和 Q4 答案通用，而且不算太難，但我犯了兩個錯誤：

不相信直覺。
沒有正確找到特殊情形。

沒時間搞特殊案例的下場就是變兩題仔。

題目

輸入長度 n 的二進制字串 s，還有整數 numOps。

你可以對 s 進行以下操作至多 numOps 次。

選擇任意索引 i，並將 s[i] 反轉。即 s[i] = ‘1’ 變成 ‘0’；反之亦然。

相同子字串指的是由只一種字元組成的子字串。

你必須將 s 的最長相同子字串的長度最小化。

求操作後可得到的最小最大長度。

解法

本來看到最大值最小化，就想到二分答案。
可是一看 Q4 題型相同，應該有更簡單的 Q3 作法，去想別的方法了。
本來想 dp 枚舉每個字元改或不改，搞半天也沒弄出來，搞到沒時間。

先想最特殊的情況，整個字串都是 1 或是 0。
如果想控制最大長度為 sz，我們每 sz+1 個字元就要把一個反轉。
若陣列長度為 x，則需要反轉 ceil(x / (sz+1))次。

推廣到交替的字串，可看作若干個子問題，分別套用上述計算。例如：

s = “1100011111”, sz = 2
可看做長度分別為 2, 3, 4 的相同字串
2 不需要反轉
3 需要反轉 1 次 4 需要反轉 1 次
共反轉 2 次

想想看，每 sz+1 格就反轉一次，有沒有可能翻到最右邊的字元，變得和下一個子字串的字元相同？例如：

s = “11100”, sz = 2
“111”，每 3 個字元就要翻一次，變成 “110”
s = “110” + “00”
操作後 s = “11000”，最大長度超過 2

其實不會，就算翻轉到最右的字元，只要改翻左邊一個就行。
前一段的長度應是 sz，改翻往左一格會使前段的連續長度變成 sz-1，例如：

s = “000” + “11”, sz = 2
“000” 原來應該翻成 “001”，改往左一格變成 “010” s =”01011”，最大長度為 2

子字串不為空，下界 lo = 1；子字串長度最大等於字串本身，上界 hi = N。
求出所有連續字元的長度，套用以上邏輯二分答案即可。

然後就錯了。
還是 hidden case，不給看。

雖然剛才討論了 s 最特殊的情形並推廣，但是忽略了最大長度 sz 的特殊情形。
其實有點小陷阱。

當 sz = 1 時，只要碰到偶數長度的子字串，反轉後就一定會和隔壁的相同。例如：

s = “0110”, sz = 1
照上述方法，兩邊的 “0” 不管，只要翻 “11”
但是翻成 “10” 或是 “01” 都會形成新的 “00”

也就是說，當 sz = 1 時，只能改成 101010… 或是 010101..，按照索引奇偶對應字元。

在二分答案前，直接枚舉 sz = 1 的兩種情況。
只要其中一種的修改次數小於 numOps，直接回傳答案 1。

時間複雜度 O(N log N)。
空間複雜度 O(N)，不預處理子字串可 O(1)。

class Solution:
    def minLength(self, s: str, numOps: int) -> int:
        N = len(s)

        # special case for sz = 1
        # try 1010.. and 0101..
        CS = "01"
        cnt = 0
        for i, c in enumerate(s):
            if ord(c)%2 == i%2:
                cnt += 1

        if min(cnt, N-cnt) <= numOps:
            return 1

        # try binary answer for greedy flip
        a = [len(list(g)) for _, g in groupby(s)]
        
        def ok(sz):
            cnt = 0
            for x in a:
                cnt += x // (sz+1)
            return cnt <= numOps

        lo = 2
        hi = N
        while lo < hi:
            mid = (lo + hi) // 2
            if not ok(mid):
                lo = mid+1
            else:
                hi = mid

        return lo

mocowcow

題目

解法