3090. Maximum Length Substring With Two Occurrences

3090. Maximum Length Substring With Two Occurrences

Difficulty: Easy

Topics: Mid Level, Hash Table, String, Sliding Window, Weekly Contest 390

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

Example 1:

• Input: s = "bcbbbcba"
• Output: 4
• Explanation: The following substring has a length of 4 and contains at most two occurrences of each character: "bcbbbcba".

Example 2:

• Input: s = "aaaa"
• Output: 2
• Explanation: The following substring has a length of 2 and contains at most two occurrences of each character: "aaaa".

Example 3:

• Input: s = "abc"
• Output: 3

Example 4:

• Input: s = "aabbcc"
• Output: 6

Example 5:

• Input: s = "ababab"
• Output: 4

Example 6:

• Input: s = "a"
• Output: 1

Example 7:

• Input: s = "zzzzz"
• Output: 2

Example 8:

• Input: s = "abcabc"
• Output: 6

Example 9:

• Input: s = "abcaabc"
• Output: 5

Constraints:

• 2 <= s.length <= 100
• s consists only of lowercase English letters.

Hint:

1. We can try all substrings by brute-force since the constraints are very small.

Solution:

We determined the optimal solution by leveraging the small input constraint (n ≤ 100) to evaluate every possible substring, tracking character frequencies, and stopping extension as soon as any character exceeds the allowed two occurrences.

Approach

• Brute‑force over all substrings – Since the string length is at most 100, we can safely check every start and end index.
• Frequency array – Maintain a count of each character (26 lowercase letters) for the current substring.
• Early termination – As we extend the substring by one character, if that character’s count becomes 3, we break because adding more characters cannot fix the violation.
• Update maximum – Before breaking or after each valid extension, update the answer with the current substring length.

Let's implement this solution in PHP: 3090. Maximum Length Substring With Two Occurrences

<?php
/**
 * @param String $s
 * @return Integer
 */
function maximumLengthSubstring(string $s): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maximumLengthSubstring("bcbbbcba") .  "\n";            // Output: 4
echo maximumLengthSubstring("aaaa") .  "\n";                // Output: 2
echo maximumLengthSubstring("abc") .  "\n";                 // Output: 3
echo maximumLengthSubstring("aabbcc") .  "\n";              // Output: 6
echo maximumLengthSubstring("ababab") .  "\n";              // Output: 4
echo maximumLengthSubstring("a") .  "\n";                   // Output: 1
echo maximumLengthSubstring("zzzzz") .  "\n";               // Output: 2
echo maximumLengthSubstring("abcabc") .  "\n";              // Output: 6
echo maximumLengthSubstring("abcaabc") .  "\n";             // Output: 5
?>

Explanation:

• Outer loop ($i) defines the starting index of the substring.
• Inner loop ($j) defines the ending index, expanding one character at a time.
• For each new character, increment its frequency.
• If the frequency of any character exceeds 2, the inner loop stops (no longer valid substring starting from $i with this $j).
• Otherwise, the current substring is valid, so we update $maxLen with $j - $i + 1.
• After the loops finish, $maxLen holds the length of the longest valid substring.

Complexity Analysis

• Time Complexity: O(n²) – For each start (n), we may iterate up to the end (n), so worst-case ~10,000 operations for n=100, which is trivial.
• Space Complexity: O(1) – We only use a fixed-size array of 26 integers regardless of input size.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub

---

1. Substring: A substring is a contiguous sequence of characters within a string. ↩