題目出處
2472. Maximum Number of Non-overlapping Palindrome Substrings
難度
hard
題目分類
Two Pointers, String, Dynamic Programming, Greedy
2026-09-15 一刷
個人範例程式碼 - 一刷 (2026/09/15)
class Solution:
def maxPalindromes(self, s: str, k: int) -> int:
count = 0
# outer loop, choose center (0, 0.5, 1, 1.5 ...)
last_end = -1
for center in range(len(s)):
for left, right in [(center, center), (center, center+1)]:
while left > last_end and right < len(s) and s[left] == s[right]:
if right - left + 1 >= k:
count += 1
last_end = right
break
left -= 1
right += 1
return count
算法說明
回文變化題
- 知道回文函式怎麼寫，有兩種 case：(center, center), (center, center+1)
- 調整中心 center
變化的地方在於，不可以有文字重疊的部分，因此我們需要隨時更新邊界，這裡我們用 last_end 來進行紀錄右邊界的位置
只要發現新的合法 >= k 長度回文，我們就把 last_end 更新為 right。
Time Complexity
O(nk)
- 其中 n 是代表外圈，center 的移動
- k 是代表處理回文的時間，因為只要能連續判斷 >= k 就可以回傳，因此最多只需要處理到 k 次
Space Complexity
O(1)