String 字串處理 ·

介紹
#

字串題大多不需要特別的演算法，難的是細節：index 的邊界、操作的先後順序、Python 字串不可變。幾個固定的寫法：

形式	做法	例子
模擬	用 list 當 stack 組結果，最後 `join`	特殊字元操作、合併相近字元
解析	每個位置嘗試比對所有 pattern，比對到就跳過	HTML entity
長度 `k` 的子字串	枚舉起點，丟進集合	所有二進位碼、三個相同數字
字元分類	母音 / 子音 / 數字分開計數	最多的母音和子音、母音排序
固定起點往右擴	增量維護計數	每種字元次數相同
切成單字	`split()` 後逐字處理	最後一個單字、Goat Latin、最常見的單字

字串上的 DP（LCS、編輯距離）見 String DP。

模板一：用 list 模擬
#

Python 字串不可變，s += c 每次都會複製。用 list 當結果，最後再 "".join：

res = []
for ch in s:
    if ch == "*":
        if res:                          # 判斷寫在裡面，不要寫成 ch == "*" and res
            res.pop()
    elif ch == "#":
        res += res
    elif ch == "%":
        res.reverse()
    else:
        res.append(ch)
return "".join(res)

特殊字元操作（LC 3612）：上面的程式。
合併相近的相同字元（LC 4019）：保留下來的字不會再變，所以只要記每種字元在結果裡最後的位置，新字元跟它的距離 <= k 就丟掉。
最大的偶數（LC 3798）：把結尾的 1 一直刪掉。

模板二：在每個位置嘗試比對
#

i, out = 0, []
while i < len(text):
    for pattern, rep in table.items():
        if text.startswith(pattern, i):  # 不會超出範圍
            out.append(rep)
            i += len(pattern)
            break
    else:
        out.append(text[i])
        i += 1

HTML entity（LC 1410）：不能用一連串的 replace：先換出來的 & 會跟後面的字組成新的 entity。
s + s 包含所有旋轉（LC 796、459）：goal 是 s 的旋轉 ⇔ 長度相同且 goal in s + s；s 有重複的週期 ⇔ s in (s + s)[1:-1]。

模板三：長度 `k` 的所有子字串
#

seen = {s[i:i + k] for i in range(len(s) - k + 1)}   # 最後一個起點是 len(s) - k

所有長度 k 的二進位碼（LC 1461）：集合大小要是 2^k；子字串數量 len(s) - k + 1 不到 2^k 就一定不夠。
三個相同的數字（LC 2264）：只有 10 種候選，從 "999" 往下檢查 in num。

模板四：字元分類計數
#

vowels = set("aeiou")
cnt = Counter(s)
best_vowel = max((cnt[c] for c in vowels), default=0)
best_consonant = max((v for c, v in cnt.items() if c not in vowels), default=0)

最多的母音加最多的子音（LC 3541）：上面的程式。
母音比子音的分數（LC 3813）：只算字母，空白和數字都不算。
依次數排序母音（LC 3913）：只把母音抽出來，用 (-次數, 第一次出現的位置) 排序後放回原本母音的位置。
前綴的不同字元數（LC 3803）：邊掃邊把字元加進集合。
相鄰數字的差（LC 3931）：直接比較相鄰兩個。

模板五：固定起點往右擴
#

for i in range(n):
    cnt = Counter()
    max_freq = 0
    for j in range(i, n):
        cnt[s[j]] += 1
        max_freq = max(max_freq, cnt[s[j]])
        if max_freq * len(cnt) == j - i + 1:     # 每種字元都出現 max_freq 次
            best = max(best, j - i + 1)

每種字元次數都相同（LC 3713）：「每種都一樣多」等於「最多的次數 × 種類數 = 長度」，每一步 O(1) 判斷。

模板六：切成單字再處理
#

words = s.split()                      # 不帶參數：連續空白當一個分隔，頭尾空白丟掉
res = []
for i, w in enumerate(words):
    res.append(轉換(w, i))
return " ".join(res)

數單字、最後一個單字（LC 434、58）：len(s.split())、s.split()[-1]。split(" ") 遇到連續空白或結尾空白會產生空字串。
逐字轉換（LC 824、557）：每個單字各自處理，需要位置時用 enumerate。
連續幾個單字（LC 1078）：檢查 words[i]、words[i + 1] 時，迴圈只跑到 len(words) - 2。
正規化再切（LC 819、929）：先把標點換成空白再切；信箱則用 @ 切成兩半，只處理前半段，接回去時保留 @。