Longest Substring with At Most Two Distinct Characters - Python Solution

1. Introduction

"Longest Substring with At Most Two Distinct Characters" is a problem that tests one's ability to manipulate and analyze strings. The challenge is to find the longest substring containing no more than two distinct characters. This problem is a variant of the more general problem of finding substrings with a given number of unique characters and requires a good grasp of sliding window techniques.

Problem

Given a string, the task is to find the length of the longest substring that contains at most two distinct characters. The solution must efficiently find the longest such substring within the given string.

2. Solution Steps

1. Use a sliding window approach to maintain a substring with at most two distinct characters.

2. Keep a hash map to count the occurrence of characters within the current window.

3. Expand the window by moving the end pointer and updating the character count.

4. If the window contains more than two distinct characters, shrink it by moving the start pointer and updating the character count.

5. Keep track of the length of the longest valid substring as the window expands and contracts.

6. Return the maximum length of the substring found.

3. Code Program

def lengthOfLongestSubstringTwoDistinct(s):
    charCount = {}
    start = maxLength = 0

    for end in range(len(s)):
        charCount[s[end]] = charCount.get(s[end], 0) + 1

        while len(charCount) > 2:
            charCount[s[start]] -= 1
            if charCount[s[start]] == 0:
                del charCount[s[start]]
            start += 1

        maxLength = max(maxLength, end - start + 1)

    return maxLength

# Example Usage
print(lengthOfLongestSubstringTwoDistinct("eceba"))  # Output: 3
print(lengthOfLongestSubstringTwoDistinct("ccaabbb")) # Output: 5

Output:

3
5

Explanation:

1. Sliding Window: Efficiently maintains a valid substring with at most two distinct characters.

2. Hash Map for Character Count: Tracks the count of each character within the current window.

3. Window Adjustment: Expands or shrinks the window based on the count of distinct characters.

4. Maximum Length Tracking: Continuously updates the length of the longest valid substring.

5. Time Complexity: The algorithm achieves O(n) time complexity, where n is the length of the string.

6. Practical Use: Demonstrates a pattern often used in string processing and substring analysis.