Longest Substring With At Most Two Distinct Characters Solution for TCS NQT

Company: TCS NQT · Difficulty: Medium · Topics: String, Sliding Window

Problem Statement

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

Examples

Example 1:

Input: s = "eceba"

Output: 3

Explanation: The substring is "ece" which its length is 3.

Example 2:

Input: s = "ccaabbb"

Output: 5

Explanation: The substring is "aabbb" which its length is 5.

Example 3:

Input: s = "a"

Output: 1

Explanation: The substring is "a" which its length is 1.

Intuition

The key insight is to use a sliding window approach with a hash table to track character frequencies. We expand the window by adding characters from the right and shrink it from the left when we have more than two distinct characters.

This approach works because:

We need to maintain at most two distinct characters in our window
When we exceed two distinct characters, we shrink the window from the left
We keep track of the maximum length found so far

Approach

Approach 1: Sliding Window with Hash Table (Optimal)

1. Use two pointers (left and right) to represent the window

2. Use a hash table to track character frequencies in the current window

3. Expand the window by moving the right pointer

4. When we have more than 2 distinct characters, shrink the window from the left

5. Keep track of the maximum length found

Approach 2: Sliding Window with Array

1. Use a fixed-size array instead of hash table for character counting

2. Since we only have lowercase letters, we can use an array of size 26

3. Same logic as hash table approach but more efficient

Approach 3: Brute Force

1. Check all possible substrings

2. For each substring, count distinct characters

3. Return the length of the longest valid substring

Dry Run

Let's trace through Example 1: s = "eceba"

Sliding Window Approach:

left=0, right=0: window="e", distinct=1, maxLen=1
left=0, right=1: window="ec", distinct=2, maxLen=2
left=0, right=2: window="ece", distinct=2, maxLen=3
left=0, right=3: window="eceb", distinct=3 → shrink left
left=1, right=3: window="ceb", distinct=3 → shrink left
left=2, right=3: window="eb", distinct=2, maxLen=3
left=2, right=4: window="eba", distinct=3 → shrink left
left=3, right=4: window="ba", distinct=2, maxLen=3

Final result: 3

Key Insights

1. Sliding Window: Expand right, shrink left when needed

2. Character Counting: Track frequency of each character in window

3. Distinct Count: Maintain count of distinct characters in window

4. Optimal Substructure: Each valid window ending at right gives us a candidate

Edge Cases

1. Single character: Return length 1

2. All same characters: Return entire string length

3. Two distinct characters: Return entire string length

4. Empty string: Return 0

Time and Space Complexity

Time Complexity: O(n) - Each character is visited at most twice
Space Complexity: O(1) - Fixed size hash table/array