Problem Description

Given a string s, you need to find the length of the longest substring where each character appears at most twice.

In other words, you're looking for the maximum length of a continuous portion of the string where no character occurs more than 2 times within that portion.

For example:

• If s = "bcbbbcba", a valid substring could be "bcbbbcb" where 'b' appears twice (at positions relative to this substring), 'c' appears twice, but if we tried to extend it further to include the final 'a', we'd still be valid. However, the substring "bcbbbc" has 'b' appearing 4 times, which exceeds the limit of 2.
• The goal is to find the longest such valid substring and return its length.

The key constraint is that within your chosen substring, every unique character must appear at most 2 times. You want to maximize the length of such a substring.

Intuition

When we need to find the longest substring with certain constraints, the sliding window technique naturally comes to mind. The key insight is that we can maintain a window that always satisfies our constraint (each character appears at most twice).

Think of it like a flexible window that we can expand and shrink as needed. We start with an empty window and gradually expand it by moving the right boundary. As we add each new character, we keep track of how many times each character appears in our current window.

The critical moment comes when adding a new character would violate our constraint - that is, when a character would appear more than twice. At this point, we can't simply skip the character because we need a continuous substring. Instead, we must shrink our window from the left side.

Here's the clever part: we don't need to shrink the window completely and start over. We only need to shrink it just enough to make it valid again. Since we just added a character that caused some character c to appear more than twice, we move the left boundary rightward, removing characters one by one, until the count of c drops back to 2.

This approach ensures that at every step, we maintain the largest valid window possible ending at the current position. By keeping track of the maximum window size we've seen throughout this process, we find our answer.

The beauty of this solution is its efficiency - we visit each character at most twice (once when expanding the window, once when shrinking it), giving us a linear time complexity. We also only need to track character counts, which requires minimal extra space.

Learn more about Sliding Window patterns.

Solution Approach

We implement the sliding window technique using two pointers to maintain a valid substring. Here's how the algorithm works:

Data Structures:

• A counter/hash map cnt to track the frequency of each character in the current window
• Two pointers: i (left boundary) and j (right boundary) of the sliding window
• A variable ans to store the maximum length found so far

Algorithm Steps:

1. Initialize the window: Start with i = 0 as the left pointer, and ans = 0 for tracking the maximum length. The counter cnt starts empty.

2. Expand the window: Iterate through the string with index j and character c:

   • Add the character to our window by incrementing cnt[c]

3. Maintain the constraint: After adding each character, check if cnt[c] > 2:

   • If yes, we need to shrink the window from the left
   • Keep moving the left pointer i rightward, decreasing the count of each character we remove (cnt[s[i]] -= 1)
   • Continue until cnt[c] <= 2 (the window becomes valid again)

4. Update the maximum: After ensuring the window is valid, calculate the current window size as j - i + 1 and update ans if this is larger than the previous maximum.

5. Return the result: After processing all characters, ans contains the maximum length of a valid substring.

Example walkthrough: For string s = "bcbbbcba":

• When we reach the 5th 'b', we have too many 'b's in our window
• We shrink from the left, removing characters until we have at most 2 'b's
• Throughout this process, we track the maximum valid window size

The time complexity is O(n) where n is the length of the string, since each character is visited at most twice (once by each pointer). The space complexity is O(k) where k is the size of the character set (at most 26 for lowercase letters or 128 for ASCII characters).

Example Walkthrough

Let's walk through the solution with s = "eceba":

Initial State:

• Left pointer i = 0, right pointer j = 0
• Counter cnt = {} (empty)
• Maximum length ans = 0

Step 1: j = 0, character = 'e'

• Add 'e' to window: cnt = {'e': 1}
• Check constraint: 'e' appears 1 time ≤ 2 ✓
• Current window: "e" (from index 0 to 0)
• Window size: 0 - 0 + 1 = 1
• Update ans = 1

Step 2: j = 1, character = 'c'

• Add 'c' to window: cnt = {'e': 1, 'c': 1}
• Check constraint: 'c' appears 1 time ≤ 2 ✓
• Current window: "ec" (from index 0 to 1)
• Window size: 1 - 0 + 1 = 2
• Update ans = 2

Step 3: j = 2, character = 'e'

• Add 'e' to window: cnt = {'e': 2, 'c': 1}
• Check constraint: 'e' appears 2 times ≤ 2 ✓
• Current window: "ece" (from index 0 to 2)
• Window size: 2 - 0 + 1 = 3
• Update ans = 3

Step 4: j = 3, character = 'b'

• Add 'b' to window: cnt = {'e': 2, 'c': 1, 'b': 1}
• Check constraint: 'b' appears 1 time ≤ 2 ✓
• Current window: "eceb" (from index 0 to 3)
• Window size: 3 - 0 + 1 = 4
• Update ans = 4

Step 5: j = 4, character = 'a'

• Add 'a' to window: cnt = {'e': 2, 'c': 1, 'b': 1, 'a': 1}
• Check constraint: 'a' appears 1 time ≤ 2 ✓
• Current window: "eceba" (from index 0 to 4)
• Window size: 4 - 0 + 1 = 5
• Update ans = 5

Result: The longest substring where each character appears at most twice is the entire string "eceba" with length 5.

Let's also trace through a case where we need to shrink the window: s = "aaabb":

Steps 1-4: Build window "aaab" with cnt = {'a': 3, 'b': 1}

• After adding the 3rd 'a' at j=2: cnt['a'] = 3 > 2 ❌
• Shrink: Remove s[0]='a', move i to 1: cnt = {'a': 2, 'b': 0}
• Now valid again with window "aa" (size = 2)

Step 5: j = 4, character = 'b'

• Add second 'b': cnt = {'a': 2, 'b': 2}
• Current window: "aabb" (from index 1 to 4)
• Window size: 4 - 1 + 1 = 4
• Final ans = 4

The algorithm efficiently maintains the largest valid window by only shrinking when necessary and only as much as needed.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s.

The algorithm uses a two-pointer sliding window approach. The outer loop iterates through each character in the string exactly once using the j pointer. The inner while loop moves the i pointer forward only when needed. Each character is visited at most twice - once by the j pointer when expanding the window and at most once by the i pointer when shrinking the window. Therefore, the total number of operations is bounded by 2n, which simplifies to O(n).

Space Complexity: O(|Σ|), where Σ is the character set.

The space is used by the Counter object cnt which stores the frequency of characters in the current window. In the worst case, the counter will contain all unique characters that appear in the string. Since the problem deals with lowercase English letters (based on the constraint that each character can appear at most 2 times in a valid substring), the character set size |Σ| = 26. Therefore, the space complexity is O(26) which simplifies to O(1) constant space, or more precisely O(|Σ|) where Σ = 26.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Inefficient Window Shrinking

The Problem: A common mistake is shrinking the window more than necessary or using a nested while loop that checks all characters in the window, not just the problematic one.

Incorrect approach:

# Wrong: Checking all characters unnecessarily
while any(count > 2 for count in char_count.values()):
    char_count[s[left]] -= 1
    if char_count[s[left]] == 0:
        del char_count[s[left]]
    left += 1

Why it's wrong: This checks every character's count in each iteration, leading to O(k) operations per shrink where k is the number of unique characters. This could degrade performance to O(n*k) overall.

Correct approach:

# Right: Only check the character that just exceeded the limit
while char_count[char] > 2:
    char_count[s[left]] -= 1
    left += 1

Pitfall 2: Forgetting to Clean Up Zero Counts

The Problem: Not removing characters with zero count from the dictionary can lead to memory inefficiency in cases with many unique characters.

Better implementation:

while char_count[char] > 2:
    char_count[s[left]] -= 1
    if char_count[s[left]] == 0:
        del char_count[s[left]]  # Clean up to save memory
    left += 1

Pitfall 3: Off-by-One Error in Window Size Calculation

The Problem: Incorrectly calculating the window size as right - left instead of right - left + 1.

Wrong:

max_length = max(max_length, right - left)  # Missing the +1

Correct:

max_length = max(max_length, right - left + 1)  # Includes both endpoints

Pitfall 4: Updating Maximum Length at Wrong Time

The Problem: Updating the maximum length before ensuring the window is valid.

Wrong:

for right, char in enumerate(s):
    char_count[char] += 1
    max_length = max(max_length, right - left + 1)  # Window might be invalid!
    while char_count[char] > 2:
        char_count[s[left]] -= 1
        left += 1

Correct:

for right, char in enumerate(s):
    char_count[char] += 1
    while char_count[char] > 2:
        char_count[s[left]] -= 1
        left += 1
    max_length = max(max_length, right - left + 1)  # Window is now valid

Pitfall 5: Using Fixed-Size Array Instead of Dictionary

The Problem: Using a fixed-size array for character counting when the character set is unknown or large.

Potentially problematic:

# Assumes only lowercase letters
char_count = [0] * 26
char_count[ord(char) - ord('a')] += 1

More robust:

# Works for any character set
char_count = Counter()
char_count[char] += 1

The dictionary approach is more flexible and handles any Unicode characters without modification, while the array approach requires knowing the exact character set beforehand.