Find Longest Special Substring That Occurs Thrice

Problem Description

You are given a string s, and your task is to find the maximum length x of a special substring that appears at least three times in s.

A special substring is defined as a substring containing only one unique character (e.g., "aaa", "bbbb").

If no such substring exists, return -1.

Approach

1. Binary Search

The problem exhibits a monotonic property:

• If a special substring of length x exists at least three times, then all substrings of length < x are also valid.
• Conversely, if x is invalid, all x > x are also invalid.

Using binary search, we efficiently search for the largest possible x:

• Start with l = 1 (minimum substring length) and r = n (length of the string s).
• Use a helper function to validate if a given x is possible.

2. Sliding Window Validation

To validate if a given x is valid:

• Use a sliding window of size x to traverse the string.
• Ensure each window contains only identical characters.
• Track occurrences of these substrings using a hashmap.
• Return true if any substring occurs at least three times.

3. Iterative Binary Search

• Perform binary search to find the largest valid x.
• If l is valid after the search, return l.
• Otherwise, return -1.

Complexity

• Time Complexity:

  • Binary Search: O(log n) iterations for a string of length n.
  • Validation for each x: O(n) using sliding window.
  • Total: O(n log n).

• Space Complexity:

  • O(n) for the hashmap used during validation.

Test Cases

Example 1

Input:

s = "aaabbbaaa"

Output:

3

Explanation:

• The substring "aaa" occurs 3 times in the string.

Example 2

Input:

s = "abc"

Output:

-1

Explanation:

• No special substring occurs at least three times.

Example 3

Input:

s = "aaaaaa"

Output:

6

Explanation:

• The substring "aaaaaa" is the entire string and appears 3 times (as a whole).

Example 4

Input:

s = "abbbbbbbc"

Output:

5

Explanation:

• The substring "bbbbb" appears at least 3 times in the string.

Example 5

Input:

s = "aabbcc"

Output:

-1

Explanation:

• No substring satisfies the condition of occurring 3 times.

Edge Cases

1. Single Character String: Input:

   s = "a"
   

   Output:

   -1
   

   Explanation: A single character cannot occur 3 times as a substring.

2. String with No Repeats: Input:

   s = "abcdef"
   

   Output:

   -1
   

   Explanation: No character repeats consecutively.

3. Already Valid Entire String: Input:

   s = "ccc"
   

   Output:

   3
   

   Explanation: The entire string forms a valid substring of length 3, occurring exactly 3 times.