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 <= 50s consists of only lowercase English letters.Problem Overview: You are given a string and need the length of the longest special substring that appears at least three times. A special substring contains only one repeating character (for example "aaa" or "bbbb"). Overlapping occurrences count, so the same region of the string can contribute to multiple substrings.
Approach 1: Sliding Window and Frequency Map (O(n) time, O(n) space)
Scan the string and group consecutive identical characters into runs such as a^3, b^2, a^4. For a run of length L, every substring length from 1..L is a valid special substring. Maintain a frequency structure for each character that counts how many times a substring of a certain length appears. While iterating through runs, update counts and track when a substring length reaches frequency ≥ 3. The key insight: special substrings are completely determined by consecutive runs, so you never need to enumerate arbitrary substrings. This approach relies on linear scans and constant-time updates using a hash table or array per character. Since each character is processed once and each run contributes limited updates, the overall complexity stays O(n) time with O(n) auxiliary space.
Approach 2: Dynamic Programming by Run Lengths (O(n^2) time, O(n) space)
Define a DP state where dp[i] stores the length of the consecutive identical-character substring ending at index i. If s[i] == s[i-1], extend the run; otherwise reset to 1. Once these run lengths are known, iterate through possible substring sizes and count how many times each length appears for the same character. When the count for a length reaches three, update the answer. This method is straightforward and easy to reason about, but checking many substring lengths leads to O(n^2) time in the worst case. It still uses only O(n) memory for the DP array. The idea combines concepts from string processing and frequency counting.
Recommended for interviews: The sliding window and run-length counting approach is the expected solution. It demonstrates that you recognize the structure of special substrings and avoid brute-force enumeration. Interviewers usually look for the observation that identical-character runs generate all valid substrings, which turns the problem into a counting task rather than substring generation. Techniques related to sliding window or binary search on substring length are common follow-ups if the problem is extended.
This approach uses a sliding window to dynamically track sequences of the same character and a frequency map to count occurrences of such sequences. The idea is to scan through the string, identify sequences where a character repeats, and use a frequency map to track how often these sequences appear. We are interested in sequences that appear at least three times.
The C solution uses a loop to iterate through the string, checking for sequences of identical characters. It keeps track of the longest such sequence and returns max_len - 2 if any sequence appears at least three times, or -1 otherwise.
Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1).
This approach uses dynamic programming to keep a matrix where DP[i][j] indicates whether substring s[i...j] is a special substring (formed by the same character). We will store the length of such substrings and check for their frequency throughout the matrix.
In this C solution, we initialize a DP table to find and store substrings that are comprised of only one type of character. By checking from each gap size, we derive substrings and see if they repeat. We adjust the maximum computed substring length if it repeats more than thrice.
Time Complexity: O(n^2), Space Complexity: O(n^2), where n is the length of the string.
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
The time complexity is O(n)
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window and Frequency Map | Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1). |
| Dynamic Programming | Time Complexity: O(n^2), Space Complexity: O(n^2), where n is the length of the string. |
| Binary Search + Sliding Window Counting | — |
| Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window and Frequency Map | O(n) | O(n) | Best general solution. Efficient for large strings and commonly expected in interviews. |
| Dynamic Programming (Run Length DP) | O(n^2) | O(n) | Useful for understanding substring counting logic or when implementing a simpler but less optimized solution. |
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 I with our built-in code editor and test cases.
Practice on FleetCode