Watch 10 video solutions for Find Longest Special Substring That Occurs Thrice II, a medium level problem involving Hash Table, String, Binary Search. This walkthrough by codestorywithMIK has 9,768 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string s that consists of lowercase English letters.
A string is called special if it is made up of only a single character. For example, the string "abc" is not special, whereas the strings "ddd", "zz", and "f" are special.
Return the length of the longest special substring of s which occurs at least thrice, or -1 if no special substring occurs at least thrice.
A substring is a contiguous non-empty sequence of characters within a string.
Example 1:
Input: s = "aaaa" Output: 2 Explanation: The longest special substring which occurs thrice is "aa": substrings "aaaa", "aaaa", and "aaaa". It can be shown that the maximum length achievable is 2.
Example 2:
Input: s = "abcdef" Output: -1 Explanation: There exists no special substring which occurs at least thrice. Hence return -1.
Example 3:
Input: s = "abcaba" Output: 1 Explanation: The longest special substring which occurs thrice is "a": substrings "abcaba", "abcaba", and "abcaba". It can be shown that the maximum length achievable is 1.
Constraints:
3 <= s.length <= 5 * 105s consists of only lowercase English letters.Problem Overview: You receive a string s. A special substring contains only one repeating character (for example "aaa" or "bbbb"). The task is to return the maximum length of a special substring that appears at least three times in the string. Overlapping occurrences count.
Approach 1: Linear Scan with Map Tracking (O(n) time, O(n) space)
Scan the string and group consecutive identical characters into runs. For example, aaabb produces runs (a,3) and (b,2). For each character, store run lengths in a map or frequency structure. The key observation: a run of length L contributes multiple substrings of smaller sizes. For a candidate length k, a run contributes L - k + 1 occurrences. By tracking the largest runs per character and aggregating their contributions, you can compute the maximum valid length where the total count reaches at least three. Hash maps make it easy to accumulate run statistics while scanning once through the string. This approach works well because the number of runs is far smaller than the number of substrings.
Approach 2: Sliding Window with Dynamic Counting (O(n log n) time, O(1) space)
Binary search the answer on substring length. For a candidate length k, verify whether any character forms a special substring of length k at least three times. Use a sliding window over the string while maintaining runs of identical characters. Each time you encounter a run of length L, compute how many windows of size k it produces: max(0, L - k + 1). Track the total occurrences per character using counters or a lightweight hash table. If any character reaches three occurrences, the candidate length is valid. Binary search over all possible lengths (1 to n) gives the maximum answer efficiently. This pattern combines binary search with substring counting.
Recommended for interviews: The linear scan with run tracking is usually preferred. It shows you recognize the structure of special substrings and avoid brute-force substring generation. Interviewers like seeing the reduction from substring enumeration to run-length aggregation. Binary search with sliding window is also acceptable, especially if you naturally frame the problem as a "check if length k works" decision problem.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan with Map Tracking | O(n) | O(n) | Best general solution. Efficient when processing long runs of identical characters. |
| Sliding Window + Binary Search | O(n log n) | O(1) | Useful when framing the problem as a length feasibility check. |