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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), Space Complexity: O(n^2), where n is the length of the string.
| 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. |
Find Longest Special Substring That Occurs Thrice I & II | Leetcode 2981 & 2982 | codestorywithMIK • codestorywithMIK • 8,401 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