Problem analysis

Given a string s, we need to find the length of the longest substring t that contains at most 2 distinct characters. This means that we get the maximum length of all possible substrings that contain up to 2 different characters.

Let's take an example to illustrate it:
consider the input string "eceba". From it, the longest substring that contains up to 2 different characters is "ece" which its length is 3. So the output for this input is 3.

Approach for solution

We can solve this problem using the sliding window technique. The key idea here is to maintain a moving window with at most two distinct characters and always try to extend it.

In our algorithm, we use a hashmap(count) to track the count of characters in the current window. We continually expand the window by moving the right pointer(r) and increasing the count for the current character. If at any point, the number of distinct characters in the window exceeds 2 (distinct > 2), we move the left pointer(l) to the right until distinct is 2 again. We update the maximum length(ans) with each move of the right pointer.

Step by step example

Let's walk through the example "eceba":

Initially, our window is empty (l=0,r=0,distinct=0,count=[],ans=0). Then, we see 'e' (increase count of 'e' in count, move r to right, distinct increase since count of 'e' becomes 1) and our window is "e", ans=1. Next, we see 'c' (increase count of 'c', move r to right, distinct increase since count of 'c' becomes 1) and our window is "ec", ans=2. Next, we see 'e' (increase count of 'e', move r to right, distinct remain the same) and our window is "ece", ans=3. Next, we see 'b' (increase count of 'b', move r to right, distinct increase since count of 'b' becomes 1) and our window is "eceb". But distinct=3 which is more than 2. Therefore, we move l to the right and decrease the count of 'e' (which is the element that l points to) in count and our window becomes "ceb". We continue this process until we reach the end of the string and return the maximum length of the substrings found.

Python Solution

1
2python
3class Solution:
4    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
5        ans = 0
6        distinct = 0
7        count = [0]*128
8            
9        l = 0
10        for r in range(len(s)):
11            if count[ord(s[r])] == 0:
12                distinct += 1
13            count[ord(s[r])] += 1
14            
15            while distinct > 2:
16                count[ord(s[l])] -= 1
17                if count[ord(s[l])] == 0:
18                    distinct -= 1
19                l += 1
20                
21            ans = max(ans, r - l + 1)
22
23        return ans

Java Solution

1
2java
3public class Solution {
4    public int lengthOfLongestSubstringTwoDistinct(String s) {
5        int ans = 0;
6        int distinct = 0;
7        int[] count = new int[128];
8
9        for (int l = 0, r = 0; r < s.length(); r++) {
10            if (++count[s.charAt(r)] == 1)
11                distinct++;
12            while (distinct == 3)
13                if (--count[s.charAt(l++)] == 0)
14                    distinct--;
15            ans = Math.max(ans, r - l + 1);
16        }
17        return ans;
18    }
19}

JavaScript Solution

1
2javascript
3class Solution {
4    lengthOfLongestSubstringTwoDistinct(s) {
5        let ans = 0;
6        let distinct = 0;
7        let count = new Array(128).fill(0);
8
9        for (let l = 0, r = 0; r < s.length; r++) {
10            if (++count[s.charCodeAt(r)] == 1)
11                distinct++;
12            while (distinct == 3)
13                if (--count[s.charCodeAt(l++)] == 0)
14                    distinct--;
15            ans = Math.max(ans, r - l + 1);
16        }
17        return ans;
18    }
19}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int lengthOfLongestSubstringTwoDistinct(string s) {
6        int ans = 0;
7        int distinct = 0;
8        vector<int> count(128);
9
10        for (int l = 0, r = 0; r < s.length(); r++) {
11            if (++count[s[r]] == 1)
12                distinct++;
13            while (distinct == 3)
14                if (--count[s[l++]] == 0)
15                    distinct--;
16            ans = max(ans, r - l + 1);
17        }
18        return ans;
19    }
20};

C# Solution

1
2csharp
3public class Solution {
4    public int LengthOfLongestSubstringTwoDistinct(string s) {
5        int ans = 0;
6        int distinct = 0;
7        int[] count = new int[128];
8
9        for (int l = 0, r = 0; r < s.Length; r++) {
10            if (++count[s[r]] == 1)
11                distinct++;
12            while (distinct == 3)
13                if (--count[s[l++]] == 0)
14                    distinct--;
15            ans = Math.Max(ans, r - l + 1);
16        }
17        return ans;
18    }
19}

While the above methods are well commented and straightforward to understand, we must remember to adjust for the character encoding if dealing with non-ASCII characters.Additionally, it’s worth noting that these solutions all solve the problem in O(n) time complexity, even though the naive approach of checking all possible substrings would have a time complexity of O(n^2). This improvement is largely due to the use of a hashmap to keep track of the frequency of characters in the current window and pointers to create a sliding window, demonstrating the power of these techniques in reducing time complexity for this type of problem.

To optimise further for space complexity, we could potentially use a hash map with just two entries for the two characters, instead of using a larger hash map or ASCII count array, since we're only interested in substrings with two distinct characters. However, this modification could result in a more complex solution as we would need additional logic to manage the hash map size.

In conclusion, when faced with a problem that requires tracking a subset of elements from a continuous sequence or an array, consider employing the sliding window technique, as it provides an efficient way to solve such problems with linear time complexity. When combined with appropriate data structures to store intermediate state, like hash maps or count arrays, it represents a powerful problem-solving approach for a wide variety of problems.