Solution Approach

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

Binary Search Template Setup

We use the standard binary search template to find the first length that does NOT work:

left, right = 1, n
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if not feasible(mid):  # length mid does NOT have 3+ occurrences
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

# first_true_index is the first infeasible length
# Answer is first_true_index - 1 (last feasible length)

The feasible(x) function returns True if length x is infeasible (no special substring of length x appears at least 3 times). This inverts the natural condition so we can use the standard "find first true" template.

Feasible Function Implementation

The feasible check 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 for each character.

2. Traverse the string with two pointers to find consecutive runs:

   i = 0
   while i < n:
       j = i + 1
       while j < n and s[j] == s[i]:
           j += 1
       # Process run from i to j-1
       i = j

3. Count special substrings in each run:

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

4. Return the inverse for template compatibility:

   return max(cnt.values()) < 3  # True if infeasible

Final Result

After binary search completes:

• If first_true_index == 1, even length 1 doesn't work, return -1
• If first_true_index == -1, all lengths work (shouldn't happen with proper bounds)
• Otherwise, return first_true_index - 1 as the maximum valid 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: left = 1, right = 13
• first_true_index = -1 (tracks first infeasible length)

Step 2: Binary Search Iterations

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

• Check if length 7 is infeasible (no special substring appears ≥ 3 times)
• Scanning the string for runs:
  • "aaa" (length 3): contributes max(0, 3-7+1) = 0 substrings
  • All runs have length ≤ 3, so no length-7 special substrings exist
• No character has 3+ occurrences → infeasible = True
• Update: first_true_index = 7, right = 6

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

• Check if length 3 is infeasible
• Scanning for runs:
  • "aaa" at position 0: contributes 3-3+1 = 1 substring "aaa"
  • "aaa" at position 4: contributes 1 substring "aaa"
  • "aaa" at position 9: contributes 1 substring "aaa"
• Count: 'a' → 3 occurrences of length-3 special substrings
• Length 3 works! → infeasible = False
• Update: left = 4

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

• Check if length 5 is infeasible
• All runs have length ≤ 3, so no length-5 special substrings exist
• infeasible = True
• Update: first_true_index = 5, right = 4

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

• Check if length 4 is infeasible
• All runs have length ≤ 3, so no length-4 special substrings exist
• infeasible = True
• Update: first_true_index = 4, right = 3

Step 3: Binary Search Termination

• left = 4 > right = 3 → loop ends
• first_true_index = 4 (first infeasible length)
• Return first_true_index - 1 = 3

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

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. Using Wrong Binary Search Template

Pitfall: Not using the standard binary search template with first_true_index tracking.

Common mistakes:

# WRONG: Using while left < right with different update rules
while left < right:
    mid = (left + right + 1) >> 1
    if check(mid):
        left = mid
    else:
        right = mid - 1

Correct approach using template:

# CORRECT: Standard template with first_true_index
left, right = 1, n
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):  # Define feasible as "condition becomes TRUE"
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

2. Incorrect Counting of Overlapping Substrings

Pitfall: Incorrectly counting how many special substrings of length x can be formed from a consecutive run.

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
• Correct count: 3 overlapping substrings at positions [0:2], [1:3], [2:4]

Correct approach:

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

3. Forgetting to Invert the Condition for "Find Maximum"

Pitfall: The template finds the first true position, but we need the last feasible position (maximum length). Must invert the condition.

Wrong:

# WRONG: feasible returns True when length works
def feasible(x):
    return max(counts.values()) >= 3  # True = works

Correct:

# CORRECT: feasible returns True when length does NOT work (infeasible)
def is_infeasible(x):
    return max(counts.values()) < 3  # True = doesn't work

# Then: first_true_index - 1 = last feasible length

4. Forgetting Edge Cases

Pitfall: Not handling when first_true_index == 1 (even length 1 is infeasible).

Wrong:

return first_true_index - 1  # Returns 0 when should return -1

Correct:

if first_true_index == 1:
    return -1  # No valid length exists
return first_true_index - 1