Longest Repeating Character Replacement
给一个字符串, 可以替换k个字符, 求替换后最长的reapting character.
这题有点难度, 需要双指针滑窗, 当找到满足的后, start应该++.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
class Solution { public int characterReplacement(String s, int k) { int start = 0; int end = 0; char max = s.charAt(0); int curMax = 0; int len = s.length(); int res = 0; int flip = 0; int sameLetter = 0; Map<Character, Integer> map = new HashMap<>(); while (start < len - k) { while (end < len && flip <= k) { char c = s.charAt(end); Integer value = map.get(c); if (value == null) { map.put(c, 1); } else { map.put(c, value + 1); } value = map.get(c); if (value > sameLetter) { max = c; sameLetter = value; } flip = end - start + 1 - sameLetter; if (flip <= k) { curMax = Math.max(curMax, end - start + 1); } end++; } res = Math.max(res, curMax); char remove = s.charAt(start); Integer i = map.get(remove); map.put(remove, i - 1); start++; // aaabb flip=0; } return res; } } |