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.
In this approach, we traverse through the string while keeping track of the maximum length of 'special' substrings (repeating characters) using a map to store occurrences. We match and compare these substrings to ensure they appear at least three times in the original string and track the maximum possible length that satisfies these conditions. Use a map or array to count substrings efficiently.
The implementation partitions the string into potential special substrings, counts each segment as it traverses, and checks subsequential matches of single characters substring. Using an integer array, we captured the longest reachable substring length that appears at least three times. The final answer represents the maximum such valid substring.
Time Complexity: O(n), where n is the length of the string, as you only pass through the string once.
Space Complexity: O(1), since the space only grows based on the number of different characters, which is constant in the English alphabet.
This approach leverages the sliding window pattern with an added dynamic counting mechanism to find potential substrings that recur thrice, making sure to handle easy reset and expansion of the window by simply expanding or shrinking based on repetition within the window. The algorithm attempts to incrementally build substrings while reverting or advancing the primary indx controller through appropriately bounded checks.
This C program navigates through the string using a sliding window approach where each window attempts to capture conjunct repeated characters limited to three-time minimal requirements. For each triple detection, progress through the string resets within conditions allowing consecutive suffix captures up to further elongation where potential and maximum length are constantly updated.
Time Complexity: O(n), as the mechanism ensures each character is analysed twice, one for window initialization and expansion through potential termination.
Space Complexity: O(1), attributed to static space limit.
We notice that if there exists a special substring of length x that appears at least three times, then a special substring of length x-1 must also exist. This exhibits a monotonicity, so we can use binary search to find the longest special substring.
We define the left boundary of the binary search as l = 0 and the right boundary as r = n, where n is the length of the string. In each binary search, we take mid = \lfloor \frac{l + r + 1}{2} \rfloor. If a special substring of length mid exists, we update the left boundary to mid. Otherwise, we update the right boundary to mid - 1. During the binary search, we use a sliding window to count the number of special substrings.
Specifically, we design a function check(x) to indicate whether a special substring of length x that appears at least three times exists.
In the function check(x), we define a hash table or an array of length 26 named cnt, where cnt[i] represents the count of special substrings of length x composed of the i-th lowercase letter. We traverse the string s. If the current character is s[i], we move the pointer j to the right until s[j] neq s[i]. At this point, s[i cdots j-1] is a special substring of length x. We increase cnt[s[i]] by max(0, j - i - x + 1), and then update the pointer i to j.
After the traversal, we go through the array cnt. If there exists cnt[i] geq 3, it means a special substring of length x that appears at least three times exists, so we return true. Otherwise, we return false.
The time complexity is O((n + |\Sigma|) times log n), and the space complexity is O(|\Sigma|), where n is the length of the string s, and |\Sigma| represents the size of the character set. In this problem, the character set is lowercase English letters, so |\Sigma| = 26.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Linear Scan with Map Tracking | Time Complexity: O(n), where n is the length of the string, as you only pass through the string once. |
| Approach 2: Sliding Window Technique with Dynamic Counting | Time Complexity: O(n), as the mechanism ensures each character is analysed twice, one for window initialization and expansion through potential termination. |
| Binary Search + Sliding Window Counting | — |
| 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. |
Find Longest Special Substring That Occurs Thrice I & II | Leetcode 2981 & 2982 | codestorywithMIK • codestorywithMIK • 9,768 views views
Watch 9 more video solutions →Practice Find Longest Special Substring That Occurs Thrice II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor