Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/424.html
424. Longest Repeating Character Replacement
Level
Medium
Description
Given a string s that consists of only uppercase English letters, you can perform at most k operations on that string.
In one operation, you can choose any character of the string and change it to any other uppercase English character.
Find the length of the longest sub-string containing all repeating letters you can get after performing the above operations.
Note:
Both the string’s length and k will not exceed 104.
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.
Solution
Use sliding window. Use a map to store each letter and the number of occurrences of each letter. Initialize low and high to 0, and use maxCount to store the maximum numbers of the same letter met so far, which is initially 0.
Loop over s using index high. Obtain the letter at index high, update the number of occurrences of the letter in the map, and update maxCount. If the current substring’s length high - low + 1 is greater than maxCount + k, then move low forward by 1 step. Move high forward by 1 step after the letter is dealt with. Finally, return s.length() - low.
-
class Solution { public int characterReplacement(String s, int k) { if (s == null || s.length() == 0) return 0; Map<Character, Integer> map = new HashMap<Character, Integer>(); int maxCount = 0; int low = 0, high = 0; int length = s.length(); while (high < length) { char highC = s.charAt(high); int highCount = map.getOrDefault(highC, 0); highCount++; map.put(highC, highCount); maxCount = Math.max(maxCount, highCount); if (high - low + 1 > maxCount + k) { char lowC = s.charAt(low); int lowCount = map.getOrDefault(lowC, 0); lowCount--; if (lowCount > 0) map.put(lowC, lowCount); else map.remove(lowC); low++; } high++; } return length - low; } } -
// OJ: https://leetcode.com/problems/longest-repeating-character-replacement/ // Time: O(N) // Space: O(1) class Solution { public: int characterReplacement(string s, int k) { int i = 0, j = 0, cnt[26] = {}, ans = 0, N = s.size(); while (j < N) { cnt[s[j++] - 'A']++; while (j - i - *max_element(cnt, cnt + 26) > k) cnt[s[i++] - 'A']--; ans = max(ans, j - i); } return ans; } }; -
class Solution: def characterReplacement(self, s: str, k: int) -> int: counter = [0] * 26 i = j = maxCnt = 0 while i < len(s): counter[ord(s[i]) - ord('A')] += 1 maxCnt = max(maxCnt, counter[ord(s[i]) - ord('A')]) if i - j + 1 > maxCnt + k: counter[ord(s[j]) - ord('A')] -= 1 j += 1 i += 1 return i - j ############ from collections import deque class Solution(object): def characterReplacement(self, s, k): """ :type s: str :type k: int :rtype: int """ ans = 0 d = {} start = 0 maxCount = 0 window = deque([]) for end in range(0, len(s)): d[s[end]] = d.get(s[end], 0) + 1 maxCount = max(maxCount, d[s[end]]) if end - start + 1 - maxCount > k: d[s[start]] -= 1 start += 1 ans = max(ans, end - start + 1) return ans -
func characterReplacement(s string, k int) int { counter := make([]int, 26) j, maxCnt := 0, 0 for i := range s { c := s[i] - 'A' counter[c]++ if maxCnt < counter[c] { maxCnt = counter[c] } if i-j+1 > maxCnt+k { counter[s[j]-'A']-- j++ } } return len(s) - j }