Posts Longest Substring with At Most Two Distinct Characters
Post
Cancel

Longest Substring with At Most Two Distinct Characters

PROBLEM DESCRIPTION

Given a string s, return the length of the longest substring that contains at most two distinct characters.

leetcode

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;

    }

}
This post is licensed under CC BY 4.0 by the author.