-
Notifications
You must be signed in to change notification settings - Fork 2
/
LongestRepeatingCharacterReplacement.java
84 lines (76 loc) · 2.49 KB
/
LongestRepeatingCharacterReplacement.java
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
package Leetcode;
import java.util.HashMap;
import java.util.Map;
/**
* @author kalpak
*
* 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 10^4.
*
* 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.
*
*/
public class LongestRepeatingCharacterReplacement {
public static int characterReplacement(String s, int k) {
if (s == null || s.length() == 0)
return 0;
Map<Character, Integer> map = new HashMap<>();
int i = 0;
int j = 0;
int maxCount = 0;
int result = 0;
while(j < s.length()) {
char c = s.charAt(j);
// calculation: put the character into the map
map.put(c, map.getOrDefault(c, 0) + 1);
// Find the maxCount
maxCount = getMaxCharFrequency(map);
// If windowSize - maxCount > k --> this means we have more characters than needed. So shrink the window
if(j - i + 1 - maxCount > k) {
while(j - i + 1 - maxCount > k) {
map.put(s.charAt(i), map.get(s.charAt(i)) - 1); // decrease the count
maxCount = getMaxCharFrequency(map); // update the maxCount
i++;
}
}
// update the result with the windowSize
result = Math.max(result, j - i + 1);
j++;
}
return result;
}
private static int getMaxCharFrequency(Map<Character, Integer> map) {
int maxCount = 0;
for(int freq : map.values()) {
maxCount = Math.max(maxCount, freq);
}
return maxCount;
}
public static void main(String[] args) {
String str1 = "ABAB";
System.out.println(characterReplacement(str1, 2));
str1 = "AABABBA";
System.out.println(characterReplacement(str1, 1));
}
}