PROBLEM DESCRIPTION
Given a string s, return the length of the longest substring that contains at most two distinct characters.
SOLUTION
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
class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
// Get the length of the input string
int n = s.length();
// Create a map to store characters and their counts
Map<Character, Integer> map = new HashMap<>();
// Initialize two pointers for the sliding window
int i=0; // Left pointer -> start of sliding window
int j=0; // Right pointer -> end of sliding window
// Initialize the maximum length of the substring with two distinct characters
int maxLength = 1;
// Start iterating through the string
while(j < n){
// Get the character at the right pointer
Character c = s.charAt(j);
// Update the character count in the map
map.put(c, map.getOrDefault(c, 0) + 1);
// Check if the number of distinct characters in the map is less than or equal to 2
if(map.size() <= 2){
// Update the maximum length if the current substring has at most two distinct characters
maxLength = Math.max(maxLength, j - i + 1);
} else {
// If there are more than two distinct characters in the map, move the left pointer (reduce windows size)
// and reduce the counts of characters until we have at most two distinct characters again.
while(map.size() > 2){
// Get the character at the left pointer
Character leftChar = s.charAt(i);
// Decrease the count of the character
map.put(leftChar, map.get(leftChar) - 1);
// If the count reaches 0, remove the character from the map
if(map.get(leftChar) == 0)
map.remove(leftChar);
// Move the left pointer to the right
i++;
}
}
// Move the right pointer to the right
j++;
}
return maxLength;
}
}