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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Length Substring With Two Occurrences

Difficulty: Easy

Problem Description

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

Key Insights

  • We need to find substrings that do not exceed two occurrences of any character.
  • A sliding window approach can efficiently track the characters and their counts.
  • As we expand the window to include new characters, we need to ensure we do not violate the character occurrence constraint.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, as we traverse the string once. Space Complexity: O(1), since the maximum number of distinct characters is limited (26 lowercase English letters).

Solution

The solution involves using a sliding window (two pointers) to maintain a substring that meets the criteria of having at most two occurrences of each character. We use a hash table (or dictionary) to keep track of the counts of each character in the current window. When we encounter a character that exceeds two occurrences, we move the left pointer to shrink the window until all characters satisfy the constraint.

Code Solutions

def maxLengthSubstring(s: str) -> int:
    char_count = {}
    left = 0
    max_length = 0

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

        # Shrink the window until all characters have at most 2 occurrences
        while char_count[s[right]] > 2:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1

        # Update the maximum length found
        max_length = max(max_length, right - left + 1)

    return max_length
← Back to All Questions