Solution Approach

The solution uses 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. Find maximal runs using two pointers:

   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 substrings: For each run of length L = j - i, we can extract max(0, L - x + 1) special substrings of length x

4. Return the inverse: Return True if no character has 3+ occurrences (infeasible)

Final Result

After binary search completes:

• If first_true_index == 1, even length 1 doesn't work, return -1
• Otherwise, return first_true_index - 1 as the maximum valid length

Example Walkthrough

Let's walk through the solution with the string s = "aaaa".

Step 1: Binary Search Initialization

• String length n = 4
• Binary search range: left = 1, right = 4
• first_true_index = -1 (tracks first infeasible length)

Step 2: Binary Search Iterations

First iteration: mid = (1 + 4) / 2 = 2

• Check if length 2 is infeasible (no 3+ occurrences)
• Run "aaaa" (length 4): contributes 4 - 2 + 1 = 3 substrings
• Count for 'a': 3 ≥ 3 → length 2 is feasible
• infeasible = False
• Update: left = 3

Second iteration: mid = (3 + 4) / 2 = 3

• Check if length 3 is infeasible
• Run "aaaa" (length 4): contributes 4 - 3 + 1 = 2 substrings
• Count for 'a': 2 < 3 → length 3 is infeasible
• infeasible = True
• Update: first_true_index = 3, right = 2

Step 3: Binary Search Termination

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

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

Another Example: s = "abcaba"

Binary Search Process:

• Initial: left = 1, right = 6, first_true_index = -1

mid = 3: Check length 3

• All runs have length 1, so max(0, 1 - 3 + 1) = 0 substrings
• infeasible = True
• Update: first_true_index = 3, right = 2

mid = 1: Check length 1

• Each run contributes 1 substring
• Count: 'a' = 3, 'b' = 2, 'c' = 1
• 'a' has 3 ≥ 3 → length 1 is feasible
• infeasible = False
• Update: left = 2

mid = 2: Check length 2

• All runs have length 1 < 2, so 0 substrings

• infeasible = True

• Update: first_true_index = 2, right = 1

• left = 2 > right = 1 → loop ends

• Return first_true_index - 1 = 1

The special substring "a" appears 3 times.

Time and Space Complexity

Time Complexity: O(n × log n)

The algorithm uses binary search on the answer range [0, 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 character segments
• For each segment, it performs constant time operations to update the count in the dictionary
• Finding the maximum value in the dictionary takes O(|Σ|) time where |Σ| = 26 for lowercase letters

Since |Σ| is constant (26), the time per check call is O(n). Therefore, the total time complexity is O(n × log n).

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

The space is used by:

• The cnt dictionary in the check function, which stores at most |Σ| entries (one for each distinct character in the string)
• Since we're dealing with lowercase English letters, |Σ| = 26, making this O(26) = O(1) constant space
• A few integer variables (i, j, l, r, mid) which use O(1) space

Therefore, the space complexity is O(|Σ|) where |Σ| = 26, which simplifies to O(1).

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