[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 (參考資料)

	class Solution {
	fun characterReplacement(s: String, k: Int): Int {
	var left = 0
	var ans = Int.MIN_VALUE
	var maxRepeatedCount = Int.MIN_VALUE
	val map = mutableMapOf<Char,Int>()
	for(right in s.indices) {
	map[s[right]] = map[s[right]]?.let {it+1} ?: 1
	maxRepeatedCount = Math.max(maxRepeatedCount, map[s[right]]!!)
	while(right - left + 1 - maxRepeatedCount > k) {
	map[s[left]] = map[s[left]]!! - 1
	++left
	}
	ans = Math.max(ans, right-left+1)
	}
	return ans
	}
	}

view raw longest_repeating_character_replacement.kt hosted with ❤ by GitHub