[LeetCode] 424. Longest Repeating Character Replacement

轉自LeetCode 

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

 

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

 

Constraints:

• 1 <= s.length <= 105
• s consists of only uppercase English letters.
• 0 <= k <= s.length

Solution

看到 string 求最長的 substring，直覺使用 sliding window

接下來就是要找怎麼縮放 window

如果沒有 k 這個限制，求最少替換次數，讓 string 都是重複的字元

求法就會是 s.length - 最多的重複字元次數，例如 ABABB

B 重複了三次，所以最少替換次數就會是 s.length - 最多的重複字元次數 = 5 - 3 = 2

因此，如果檢查到 sliding widonw size - 最多的重複字元次數 > k 的時候，就要開始縮小 window

kotlin (參考資料)