Problem Description

You are given a string s consisting of lowercase English letters.

A special string is defined as a string made up of only a single character. For example:

• "abc" is not special (contains different characters)
• "ddd" is special (all characters are 'd')
• "zz" is special (all characters are 'z')
• "f" is special (single character)

Your task is to find the length of the longest special substring of s that occurs at least three times in the string.

A substring is a contiguous non-empty sequence of characters within a string.

Return:

• The length of the longest special substring that appears at least 3 times
• -1 if no such special substring exists

For example, if you have a string where the substring "aa" appears 3 or more times in different positions, and this is the longest such special substring, you would return 2.

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 we can simply trim one character from each occurrence of the length x substring to get occurrences of length x-1.

For example, if "aaa" appears 3 times in the string, 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 a certain length that appear 3+ times, we should try longer lengths. If we can't, we should try shorter lengths.

For checking if a given length x works, we need to count how many times special substrings of length x appear. We can do this efficiently by:

1. Finding all maximal runs of the same character (like "aaaa" or "bbb")
2. For each run of length L, we can extract max(0, L - x + 1) special substrings of length x

For instance, from "aaaaa" (length 5), we can extract:

• If x = 3: we get 3 substrings ("aaa" starting at positions 0, 1, and 2)
• If x = 4: we get 2 substrings ("aaaa" starting at positions 0 and 1)
• If x = 6: we get 0 substrings (run is too short)

By counting these for each character and checking if any character's count reaches 3, we can determine if length x is achievable.

Learn more about Binary Search and Sliding Window patterns.

Solution Approach

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

Binary Search Setup:

• Initialize search boundaries: l = 0 (left) and r = n (right), where n is the string length
• For each iteration, calculate mid = (l + r + 1) >> 1 (equivalent to (l + r + 1) // 2)
• If a special substring of length mid exists with 3+ occurrences, update l = mid (search for longer)
• Otherwise, update r = mid - 1 (search for shorter)
• Continue until l >= r

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

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

2. Find maximal runs: Use two pointers i and j to identify consecutive runs of the same character:

   i = 0
   while i < n:
       j = i + 1
       while j < n and s[j] == s[i]:
           j += 1
       # Now s[i:j] is a maximal run of the same character

3. Count substrings: For each maximal run from position i to j-1:

   • The run has length j - i
   • From this run, we can extract max(0, j - i - x + 1) special substrings of length x
   • Add this count to cnt[s[i]]

4. Check threshold: After processing all runs, return True if any character has cnt[character] >= 3

Final Result:

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

Example Walkthrough: For string "aaabbbccc" checking length x = 2:

• Run "aaa" (length 3): contributes 3 - 2 + 1 = 2 substrings of "aa"
• Run "bbb" (length 3): contributes 3 - 2 + 1 = 2 substrings of "bb"
• Run "ccc" (length 3): contributes 3 - 2 + 1 = 2 substrings of "cc"
• None reach count of 3, so check(2) returns False

Example Walkthrough

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

Step 1: Binary Search Initialization

• String length n = 4
• Search boundaries: l = 0, r = 4

Step 2: First Binary Search Iteration

• Calculate mid = (0 + 4 + 1) >> 1 = 2
• Check if special substrings of length 2 appear at least 3 times

Checking length 2:

• Find maximal run: "aaaa" (positions 0 to 3)
• Run length = 4
• Number of length-2 substrings: max(0, 4 - 2 + 1) = 3
• These are: "aa" at position 0, "aa" at position 1, "aa" at position 2
• Count for character 'a': 3
• Since 3 ≥ 3, check(2) returns True
• Update l = 2 (search for longer substrings)

Step 3: Second Binary Search Iteration

• New boundaries: l = 2, r = 4
• Calculate mid = (2 + 4 + 1) >> 1 = 3
• Check if special substrings of length 3 appear at least 3 times

Checking length 3:

• Find maximal run: "aaaa" (positions 0 to 3)
• Run length = 4
• Number of length-3 substrings: max(0, 4 - 3 + 1) = 2
• These are: "aaa" at position 0, "aaa" at position 1
• Count for character 'a': 2
• Since 2 < 3, check(3) returns False
• Update r = 3 - 1 = 2

Step 4: Binary Search Termination

• Now l = 2, r = 2
• Since l >= r, binary search ends
• Return l = 2 as the answer

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

Another Example: s = "abcaba"

Binary Search Process:

• Initial: l = 0, r = 6

• mid = 3: Check length 3

  • Maximal runs: "a", "b", "c", "a", "b", "a"
  • Each run has length 1, so max(0, 1 - 3 + 1) = 0 substrings
  • check(3) returns False
  • Update r = 2

• mid = 1: Check length 1

  • Maximal runs contribute:
    • "a": 1 substring (appears at position 0)
    • "b": 1 substring (appears at position 1)
    • "c": 1 substring (appears at position 2)
    • "a": 1 substring (appears at position 3)
    • "b": 1 substring (appears at position 4)
    • "a": 1 substring (appears at position 5)
  • Count: 'a' appears 3 times, 'b' appears 2 times, 'c' appears 1 time
  • Since 'a' count = 3 ≥ 3, check(1) returns True
  • Update l = 1

• Binary search ends with l = 1

• Return 1 (the special substring "a" appears 3 times)

Solution Implementation

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. Misunderstanding "Special Substring" Definition

Many developers incorrectly assume that we need to find any substring that appears 3+ times, rather than a substring consisting of only repeated characters.

Wrong Interpretation:

# Incorrectly counts ALL substrings, not just special ones
def check_wrong(x):
    substrings = defaultdict(int)
    for i in range(len(s) - x + 1):
        substrings[s[i:i+x]] += 1
    return max(substrings.values()) >= 3

Correct Approach: Only count substrings where all characters are the same. The solution correctly handles this by processing maximal runs of identical characters.

2. Off-by-One Error in Counting Substrings

When calculating how many substrings of length x can be extracted from a run of length n, the formula is max(0, n - x + 1), not n - x.

Common Mistake:

# Missing the +1 in the formula
possible_substrings = max(0, group_length - target_length)  # Wrong!

Correct Formula:

possible_substrings = max(0, group_length - target_length + 1)

For example, from "aaa" (length 3), we can extract:

• 2 substrings of length 2: "aa" at positions [0,1] and [1,2]
• Formula: 3 - 2 + 1 = 2 ✓

3. Binary Search Boundary Issues

Using standard binary search pattern mid = (left + right) // 2 can cause infinite loops when searching for maximum valid values.

Problematic Pattern:

while left < right:
    mid = (left + right) // 2  # Can cause infinite loop
    if check(mid):
        left = mid  # When left = right - 1, mid always equals left
    else:
        right = mid - 1

Solution: Use ceiling division mid = (left + right + 1) // 2 or the bit shift equivalent (left + right + 1) >> 1 to ensure progress when left = right - 1.

4. Inefficient Character Group Detection

Processing each character individually instead of identifying maximal runs leads to incorrect counting.

Inefficient/Wrong:

for i in range(len(s)):
    if i == 0 or s[i] != s[i-1]:
        # Start new group - but doesn't track full group length
        count = 1
    else:
        count += 1
    # Can't correctly calculate substrings without knowing total group length

Correct Two-Pointer Approach:

i = 0
while i < len(s):
    j = i + 1
    while j < len(s) and s[j] == s[i]:
        j += 1
    # Now we know the complete group s[i:j] before processing
    group_length = j - i
    # Process entire group at once
    i = j

5. Forgetting Edge Cases

Not handling the case where no valid special substring exists (should return -1).

Missing Edge Case Handling:

# Wrong: always returns a value even when no valid substring exists
return left

Correct Implementation:

return -1 if left == 0 else left

This ensures that when binary search converges to 0 (meaning even length-1 special substrings don't appear 3+ times), we correctly return -1.