NUHMAN.com

Introduction

LeetCode 159 asks us to find the length of the longest substring in a given string that contains at most two distinct characters. This is a typical sliding window problem where we need to efficiently manage the window and track the distinct characters that appear in it. The goal is to return the length of the longest such substring.

Problem Statement

Given a string s, the task is to find the length of the longest substring that contains at most two distinct characters. You need to implement the following function:

go

func lengthOfLongestSubstringTwoDistinct(s string) int

• Input: A string s consisting of lowercase English letters.
• Output: The length of the longest substring that contains at most two distinct characters.

Approach

Key Idea:

To solve this problem efficiently, we can use the sliding window technique combined with a hashmap to keep track of the count of distinct characters in the current window. The window will be expanded until there are more than two distinct characters, at which point we will shrink the window from the left to ensure it contains at most two distinct characters.

Steps:

1. Initialize Two Pointers: Use two pointers, left and right, to define the window's bounds. Start both pointers at the beginning of the string.
2. Expand the Window: Expand the window by moving the right pointer to the right, adding characters to the window.
3. Track Distinct Characters: Use a hashmap (or a dictionary) to track the counts of the characters in the current window.
4. Shrink the Window: If the number of distinct characters in the window exceeds two, increment the left pointer to shrink the window and remove characters until there are at most two distinct characters.
5. Calculate the Length: Keep track of the maximum length of valid windows (those containing at most two distinct characters).

Go Implementation

go

func lengthOfLongestSubstringTwoDistinct(s string) int {
    // Initialize the variables for the sliding window
    left := 0
    maxLen := 0
    charCount := make(map[byte]int)
    
    // Iterate through the string with the right pointer
    for right := 0; right < len(s); right++ {
        // Add the current character to the map and increase its count
        charCount[s[right]]++
        
        // If we have more than 2 distinct characters, move the left pointer
        // to shrink the window
        for len(charCount) > 2 {
            charCount[s[left]]--
            if charCount[s[left]] == 0 {
                delete(charCount, s[left])
            }
            left++ // Shrink the window from the left
        }
        
        // Update the maximum length of the window with at most two distinct characters
        maxLen = max(maxLen, right-left+1)
    }
    
    return maxLen
}

// Helper function to find the maximum of two integers
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation of the Code:

1. Sliding Window:

• The sliding window is represented by two pointers: left and right. We start both pointers at the beginning of the string.
• The right pointer expands the window by iterating through the string, while the left pointer may shrink the window when there are more than two distinct characters.

2. Hashmap (charCount):

• We use a hashmap (charCount) to store the count of each character in the current window. This allows us to efficiently track how many distinct characters are in the window.

3. Shrinking the Window:

• If the window contains more than two distinct characters (i.e., the size of the hashmap exceeds 2), we increment the left pointer to shrink the window from the left side. For each character removed from the window, we decrease its count in the hashmap and remove it from the hashmap when its count reaches zero.

4. Maximizing the Length:

• As we expand and shrink the window, we continuously update the maxLen variable, which stores the length of the longest valid window found so far.

5. Time and Space Complexity:

OperationComplexitySliding WindowO(n)Hashmap OperationsO(1) per operationOverallO(n)

• Time Complexity: Each character in the string is processed at most twice (once when the right pointer expands and once when the left pointer shrinks), so the time complexity is O(n), where n is the length of the string.
• Space Complexity: The space complexity is O(1) because the hashmap can contain at most 2 distinct characters at any time (the number of distinct characters is bounded by 2).

Example

Example 1:

go

s := "eceba"
result := lengthOfLongestSubstringTwoDistinct(s)
fmt.Println(result)  // Output: 3

Explanation:

• The longest substring with at most two distinct characters is "ece", which has a length of 3. Therefore, the result is 3.

Example 2:

go

s := "ccaabbb"
result := lengthOfLongestSubstringTwoDistinct(s)
fmt.Println(result)  // Output: 5

Explanation:

• The longest substring with at most two distinct characters is "aabbb", which has a length of 5. Therefore, the result is 5.

Conclusion

LeetCode 159 challenges us to find the longest substring containing at most two distinct characters using an efficient sliding window approach. By maintaining a hashmap to track character counts and using two pointers (left and right), we can solve this problem in O(n) time and O(1) space. This solution is optimal and leverages the sliding window technique effectively.