2982. Find Longest Special Substring That Occurs Thrice II LeetCode Solution
In this guide, you will get 2982. Find Longest Special Substring That Occurs Thrice II LeetCode Solution with the best time and space complexity. The solution to Find Longest Special Substring That Occurs Thrice II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find Longest Special Substring That Occurs Thrice II
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.
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 * 105
s consists of only lowercase English letters.
Complexity Analysis
Time Complexity: O(26n) = O(n)
Space Complexity: O(26n) = O(n)
2982. Find Longest Special Substring That Occurs Thrice II LeetCode Solution in C++
class Solution {
public:
int maximumLength(string s) {
const int n = s.length();
int ans = -1;
int runningLen = 0;
char prevLetter = '@';
// counts[i][j] := the frequency of ('a' + i) repeating j times
vector<vector<int>> counts(26, vector<int>(n + 1));
for (const char c : s)
if (c == prevLetter) {
++counts[c - 'a'][++runningLen];
} else {
runningLen = 1;
++counts[c - 'a'][runningLen];
prevLetter = c;
}
for (const vector<int>& count : counts)
ans = max(ans, getMaxFreq(count, n));
return ans;
}
private:
// Returns the maximum frequency that occurs more than three times.
int getMaxFreq(const vector<int>& count, int maxFreq) {
int times = 0;
for (int freq = maxFreq; freq >= 1; --freq) {
times += count[freq];
if (times >= 3)
return freq;
}
return -1;
}
}; /* code provided by PROGIEZ */
2982. Find Longest Special Substring That Occurs Thrice II LeetCode Solution in Java
class Solution {
public int maximumLength(String s) {
final int n = s.length();
int ans = -1;
int runningLen = 0;
char prevLetter = '@';
// counts[i][j] := the frequency of ('a' + i) repeating j times
int[][] counts = new int[26][n + 1];
for (final char c : s.toCharArray())
if (c == prevLetter) {
++counts[c - 'a'][++runningLen];
} else {
runningLen = 1;
++counts[c - 'a'][runningLen];
prevLetter = c;
}
for (int[] count : counts) {
ans = Math.max(ans, getMaxFreq(count, n));
}
return ans;
}
// Returns the maximum frequency that occurs more than three times.
private int getMaxFreq(int[] count, int maxFreq) {
int times = 0;
for (int freq = maxFreq; freq >= 1; --freq) {
times += count[freq];
if (times >= 3)
return freq;
}
return -1;
}
} // code provided by PROGIEZ
2982. Find Longest Special Substring That Occurs Thrice II LeetCode Solution in Python
class Solution:
def maximumLength(self, s: str) -> int:
n = len(s)
runningLen = 0
prevLetter = '@'
# counts[i][j] := the frequency of ('a' + i) repeating j times
counts = [[0] * (n + 1) for _ in range(26)]
for c in s:
if c == prevLetter:
runningLen += 1
counts[ord(c) - ord('a')][runningLen] += 1
else:
runningLen = 1
counts[ord(c) - ord('a')][runningLen] += 1
prevLetter = c
def getMaxFreq(count: list[int]) -> int:
"""Returns the maximum frequency that occurs more than three times."""
times = 0
for freq in range(n, 0, -1):
times += count[freq]
if times >= 3:
return freq
return -1
return max(getMaxFreq(count) for count in counts) # code by PROGIEZ
