LeetCode 解題紀錄 1156. Swap For Longest Repeated Character Substring

Swap For Longest Repeated Character Substring - LeetCode

題目

給定一個字串 text，找出最長的重複字元子字串長度，可以交換一個字元

限制

• 1≤ text.length ≤ 2*10⁴

觀察

• 使用 sliding window 來追蹤最長的重複次字串

思路

• 兩段中間差一個字重複子字串，可以透過交換一個字元合併成更長的子字 串
• 如果其他地方還有一樣的字元，則可以交換該字元，長度加 1
• 利用長度編碼方式，將重複字元視為一個 group，方便處理

Trial 1

結果

TC：O(n)， SC：O(n) 程式碼有點冗長

Trial 2

• 參考別人的作法，先計算所有字元出現的次數
• 從頭開始搜尋重複字元，找到時試著跳過一個字元找尋下一段重複字元
• 如果這兩段子字串長度小於總次數，則可以加 1

結果

TC 不變，SC 降為 O(1)，程式碼變得更加精簡有效率