We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Length Substring With Two Occurrences

Number: 3349

Difficulty: Easy

Paid? No

Companies: Walmart Labs

Problem Description

Given a string s consisting of lowercase English letters, return the maximum length of a substring such that it contains at most two occurrences of each character.

Key Insights

  • The problem is a sliding window problem where we maintain a window that satisfies the constraint (each character appears at most twice).
  • Use a hash table (or dictionary) to track the count of each character in the current window.
  • Expand the window with the right pointer until a character count exceeds two.
  • When the constraint is violated, move the left pointer to reduce counts until the window becomes valid.
  • Update the maximum length during valid window intervals.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, because each element is processed at most twice. Space Complexity: O(1), as the frequency dictionary only stores counts for 26 lowercase English letters.

Solution

We use the sliding window approach by maintaining two pointers (left and right) and a frequency map (or hash table) to keep track of the count of each character in the current window. Start by moving the right pointer to include new characters. If adding a new character leads to its count exceeding 2, increment the left pointer until the count is corrected. During each valid window, update the maximum window length if needed. This ensures we check all potential substrings while keeping the solution efficient.

Code Solutions

# Python solution using sliding window and dictionary for character counts.
def max_length_substring(s: str) -> int:
    left = 0
    max_length = 0
    char_counts = {}  # Dictionary to store the count of each char
    
    for right in range(len(s)):
        # Increase the count for the current character at right pointer.
        char_counts[s[right]] = char_counts.get(s[right], 0) + 1
        
        # If any character appears more than twice, shrink the window from the left.
        while char_counts[s[right]] > 2:
            char_counts[s[left]] -= 1
            left += 1
        
        # Update maximum length for valid window [left, right].
        max_length = max(max_length, right - left + 1)
    
    return max_length

# Example call:
print(max_length_substring("bcbbbcba"))  # Expected output: 4
← Back to All Questions