424. Longest Repeating Character Replacement - Medium
Given a 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: 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. ? sliding window time = O(n),space = O(1) class Solution { public int characterReplacement(String s,int k) { int[] count = new int[26]; // maxCount: max # of unique characters in the current window int slow = 0,fast = 0,counter = 0,maxCount = 0,maxLen = 0; while(fast < s.length()) { count[s.charAt(fast) - ‘A‘]++; maxCount = Math.max(maxCount,count[s.charAt(fast) - ‘A‘]); fast++; // end - start - maxCount: # of characters that are NOT the character that occurs the most in the window while(fast - slow - maxCount > k) { count[s.charAt(slow) - ‘A‘]--; slow++; } maxLen = Math.max(maxLen,fast - slow); } return maxLen; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |