Problem Description

You need to find the length of the longest "special substring" that appears at least 3 times in a given string s.

A special substring is defined as a substring that consists of only a single repeated character. For example:

• "aaa" is special (all 'a's)
• "bb" is special (all 'b's)
• "abc" is NOT special (different characters)

The task is to:

1. Find all possible special substrings in the string s
2. Identify which of these special substrings occur at least 3 times
3. Return the length of the longest such substring

If no special substring appears at least 3 times, return -1.

Example walkthrough:

• If s = "aaaa", the special substrings are:

  • "a" appears 4 times
  • "aa" appears 3 times
  • "aaa" appears 2 times
  • "aaaa" appears 1 time

  The longest special substring appearing at least 3 times is "aa" with length 2.

Key points:

• The string s consists only of lowercase English letters
• A substring must be contiguous (consecutive characters)
• The same special substring can overlap in different occurrences
• You're looking for the maximum length among all qualifying special substrings

Intuition

The key observation is that if a special substring of length x appears at least 3 times, then a special substring of length x-1 must also appear at least 3 times. This is because any substring of length x contains multiple substrings of length x-1.

For example, if "aaa" appears 3 times, then "aa" must appear at least 3 times (actually more, since each "aaa" contains two "aa" substrings).

This monotonic property suggests we can use binary search on the answer. If we can find special substrings of length mid appearing at least 3 times, we should search for longer ones. If not, we need to search for shorter ones.

To efficiently count occurrences of special substrings of a given length, we can use a sliding window approach. When we encounter a consecutive run of the same character (like "aaaaa"), we can calculate how many special substrings of length x it contains:

• A run of length L contains max(0, L - x + 1) special substrings of length x
• For example, "aaaaa" (length 5) contains 3 substrings of length 3: starting at positions 0, 1, and 2

The algorithm combines these two ideas:

1. Binary search on the length of the special substring (from 0 to n)
2. For each candidate length, scan through the string to find all runs of identical characters
3. Count how many special substrings of that length each run contributes
4. Check if any character has at least 3 special substrings of that length

This approach efficiently narrows down to the maximum valid length without having to explicitly enumerate all possible substrings.

Learn more about Binary Search and Sliding Window patterns.

Solution Approach

The solution implements a binary search combined with a sliding window counting technique.

Binary Search Setup

We set up binary search boundaries:

• l = 0: minimum possible length (represents no valid substring)
• r = n: maximum possible length (entire string)

We search for the maximum length where a special substring appears at least 3 times using the pattern:

while l < r:
    mid = (l + r + 1) >> 1  # equivalent to (l + r + 1) // 2
    if check(mid):
        l = mid  # valid length found, search for longer
    else:
        r = mid - 1  # invalid, search for shorter

Check Function Implementation

The check(x) function determines if there exists a special substring of length x appearing at least 3 times:

1. Initialize a counter: Use defaultdict(int) to count occurrences of special substrings for each character.

2. Traverse the string with two pointers:

   i = 0
   while i < n:
       j = i + 1
       while j < n and s[j] == s[i]:
           j += 1

   This finds consecutive runs of the same character s[i].

3. Count special substrings in each run:

   • For a run from position i to j-1 (length = j - i)
   • Number of special substrings of length x = max(0, j - i - x + 1)
   • Add this count to cnt[s[i]]

4. Check if any character has enough occurrences:

   return max(cnt.values()) >= 3

Example Walkthrough

For string "aaabbbccc" checking length x = 2:

• First run: "aaa" (length 3) → contributes 3 - 2 + 1 = 2 substrings of "aa"
• Second run: "bbb" (length 3) → contributes 3 - 2 + 1 = 2 substrings of "bb"
• Third run: "ccc" (length 3) → contributes 3 - 2 + 1 = 2 substrings of "cc"
• None appear 3 times, so check(2) returns false

Final Result

After binary search completes:

• If l == 0, no valid special substring exists, return -1
• Otherwise, return l as the maximum length

The time complexity is O(n log n) where each binary search iteration takes O(n) time to scan the string.

Example Walkthrough

Let's walk through the solution with s = "aaabaaabcaaab".

Step 1: Binary Search Setup

• String length n = 13
• Binary search range: l = 0, r = 13

Step 2: Binary Search Iterations

First iteration: mid = (0 + 13 + 1) / 2 = 7

• Check if any special substring of length 7 appears ≥ 3 times
• Scanning the string for runs:
  • "aaa" (length 3): contributes max(0, 3-7+1) = 0 substrings
  • "b" (length 1): contributes 0 substrings
  • "aaa" (length 3): contributes 0 substrings
  • "b" (length 1): contributes 0 substrings
  • "c" (length 1): contributes 0 substrings
  • "aaa" (length 3): contributes 0 substrings
  • "b" (length 1): contributes 0 substrings
• No character has 3+ occurrences → check(7) = false
• Update: r = 6

Second iteration: mid = (0 + 6 + 1) / 2 = 3

• Check if any special substring of length 3 appears ≥ 3 times
• Scanning for runs:
  • "aaa" at position 0: contributes 3-3+1 = 1 substring "aaa"
  • "b" at position 3: contributes 0 substrings
  • "aaa" at position 4: contributes 1 substring "aaa"
  • "b" at position 7: contributes 0 substrings
  • "c" at position 8: contributes 0 substrings
  • "aaa" at position 9: contributes 1 substring "aaa"
  • "b" at position 12: contributes 0 substrings
• Count: 'a' → 3 occurrences of length-3 special substrings
• check(3) = true → Update: l = 3

Third iteration: mid = (3 + 6 + 1) / 2 = 5

• Check if any special substring of length 5 appears ≥ 3 times
• All runs have length ≤ 3, so no length-5 special substrings exist
• check(5) = false → Update: r = 4

Fourth iteration: mid = (3 + 4 + 1) / 2 = 4

• Check if any special substring of length 4 appears ≥ 3 times
• All runs have length ≤ 3, so no length-4 special substrings exist
• check(4) = false → Update: r = 3

Step 3: Binary Search Termination

• l = 3, r = 3 → loop ends
• Return l = 3

The answer is 3 because "aaa" appears exactly 3 times in the string, making it the longest special substring that meets the requirement.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The algorithm uses binary search on the answer space from 0 to n, which takes O(log n) iterations. In each iteration, the check function is called.

The check function iterates through the string once with two pointers (i and j), taking O(n) time to identify consecutive segments of identical characters. For each segment, it performs constant-time operations to update the count in the dictionary. The max(cnt.values()) operation at the end takes O(|Σ|) time where |Σ| is the size of the character set (26 for lowercase English letters).

Since |Σ| = 26 is a constant and n dominates, the time complexity per check call is O(n). Therefore, the overall time complexity is O(n × log n).

Space Complexity: O(|Σ|) or O(1)

The space is primarily used by the cnt dictionary in the check function, which stores at most |Σ| entries (one for each distinct character in the string). Since |Σ| = 26 for lowercase English letters, this is effectively O(1) constant space.

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

Common Pitfalls

1. Incorrect Counting of Overlapping Substrings

Pitfall: A common mistake is incorrectly counting how many special substrings of length x can be formed from a consecutive run of the same character. Developers often forget that substrings can overlap.

Incorrect approach:

# WRONG: Dividing the group length by target length
possible_substrings = group_length // target_length

Why it's wrong: For a run like "aaaa" (length 4) and target length 2:

• Wrong calculation: 4 // 2 = 2 (suggests only 2 substrings)
• Correct count: We actually have 3 overlapping substrings: "aa" at positions [0:2], [1:3], [2:4]

Correct approach:

# CORRECT: Using sliding window formula
possible_substrings = max(0, group_length - target_length + 1)

2. Binary Search Boundary Issues

Pitfall: Using the wrong binary search template or incorrect mid calculation can lead to infinite loops or missing the correct answer.

Common mistakes:

# WRONG: May cause infinite loop when l+1 == r
mid = (left + right) // 2

# WRONG: May miss the maximum valid value
while left <= right:  # Using <= instead of <
    mid = (left + right) // 2
    if check(mid):
        left = mid + 1  # Skipping the valid answer
    else:
        right = mid - 1

Correct approach:

# CORRECT: Upper mid formula prevents infinite loops
mid = (left + right + 1) >> 1  # or (left + right + 1) // 2

# CORRECT: Maintains invariant that left is always valid (or 0)
while left < right:
    mid = (left + right + 1) >> 1
    if check(mid):
        left = mid  # Keep the valid answer
    else:
        right = mid - 1

3. Forgetting Edge Cases

Pitfall: Not handling the case where no valid substring exists.

Wrong:

# WRONG: Always returns a positive number
return left  # What if left is still 0?

Correct:

# CORRECT: Check if we found any valid substring
return -1 if left == 0 else left

4. Inefficient Character Group Detection

Pitfall: Using nested loops or regex to find consecutive character groups, leading to O(n²) complexity.

Inefficient approach:

# WRONG: O(n²) time complexity
for i in range(n):
    for j in range(i+1, n+1):
        if all(s[k] == s[i] for k in range(i, j)):
            # Process group

Efficient approach:

# CORRECT: O(n) single pass with two pointers
i = 0
while i < n:
    j = i + 1
    while j < n and s[j] == s[i]:
        j += 1
    # Process group from i to j-1
    i = j

Complete Corrected Solution:

from collections import defaultdict

class Solution:
    def maximumLength(self, s: str) -> int:
        def check(x):
            if x == 0:  # Edge case: length 0 is invalid
                return False
              
            cnt = defaultdict(int)
            i = 0
            n = len(s)
          
            while i < n:
                j = i + 1
                while j < n and s[j] == s[i]:
                    j += 1
              
                # Correct sliding window count
                group_length = j - i
                cnt[s[i]] += max(0, group_length - x + 1)
                i = j
          
            return cnt and max(cnt.values()) >= 3  # Handle empty cnt
      
        n = len(s)
        left, right = 0, n
      
        # Correct binary search with upper mid
        while left < right:
            mid = (left + right + 1) >> 1
            if check(mid):
                left = mid
            else:
                right = mid - 1
      
        # Handle no valid substring case
        return -1 if left == 0 else left