Find Longest Special Substring That Occurs Thrice II solution and explanation
Google
9 more videos on this problem
Find Longest Special Substring That Occurs Thrice I & II | Leetcode 2981 & 2982 | codestorywithMIKcodestorywithMIK · 58:52 · 10K views
Find Longest Special Substring That Occurs Thrice I and II | Leetcode 2982 | Leetcode 2981Techdose · 27:37 · 6K views
2982. Find Longest Special Substring That Occurs Thrice II | 3 Approaches | HashMap | ArraysAryan Mittal · 23:48 · 3K views
Find Longest Special Substring That Occurs Thrice II - LEETCODE WEEKLY CONTEST 378Joyjit Codes · 9:31 · 1K views
Find Longest Special Substring That Occurs Thrice II - PythonCheatCode Ninja · 12:02 · 1K views
2982. Find Longest Special Substring That Occurs Thrice II || 2891 | Weekly Leetcode 378codingMohan · 41:18 · 1K views
2982. Find Longest Special Substring That Occurs Thrice II | Binary Search | Weekly 378Tech Courses · 19:20 · 1K views
2982. Find Longest Special Substring That Occurs Thrice II Weekly Contest 378 || LeetcodeGeekstocode · 15:56 · 1K views
2982. Find Longest Special Substring That Occurs Thrice II (Leetcode Medium)Programming Live with Larry · 14:39 · 785 views
LeetCode 2982 - Find Longest Special Substring That Occurs Thrice II - PythonAlpha-Code · 21:20 · 228 views
The problem
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 * 105sconsists of only lowercase English letters.
Approach overview
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 1: Approach 1: Linear Scan with Map Tracking
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.
def longestSpecialSubstring(s):
max_length = -1
for char in 'abcdefghijklmnopqrstuvwxyz':
count, max_for_char = 0, 0
for c in s:
if c == char:
count += 1
else:
if count >= 3:
max_for_char = max(max_for_char, count)
count = 0
if count >= 3:
max_for_char = max(max_for_char, count)
if max_for_char >= 3:
max_length = max(max_length, max_for_char)
return max_length
print(longestSpecialSubstring("abcaba")) # Output: 1public class Main {
public static int longestSpecialSubstring(String s) {
int n = s.length();
int max_length = -1;
for (char ch = 'a'; ch <= 'z'; ++ch) {
int count = 0;
int max_for_char = 0;
for (char c : s.toCharArray()) {
if (c == ch) {
count++;
} else {
if (count >= 3) max_for_char = Math.max(max_for_char, count);
count = 0;
}
}
if (count >= 3) max_for_char = Math.max(max_for_char, count);
if (max_for_char >= 3) max_length = Math.max(max_length, max_for_char);
}
return max_length;
}
public static void main(String[] args) {
String s = "abcaba";
System.out.println(longestSpecialSubstring(s)); // Output: 1
}
}#include <iostream>
#include <string>
#include <unordered_map>
int longestSpecialSubstring(std::string s) {
int max_length = -1;
for (char current = 'a'; current <= 'z'; ++current) {
int max_for_char = 0, count = 0;
for (char c : s) {
if (c == current) {
count++;
} else {
if (count >= 3) max_for_char = std::max(max_for_char, count);
count = 0;
}
}
if (count >= 3) max_for_char = std::max(max_for_char, count);
if (max_for_char >= 3) max_length = std::max(max_length, max_for_char);
}
return max_length;
}
int main() {
std::string str = "abcaba";
std::cout << longestSpecialSubstring(str); // Output: 1
return 0;
}function longestSpecialSubstring(s) {
let maxLength = -1;
for (let ch = 97; ch <= 122; ch++) { // 'a' to 'z'
let count = 0;
let maxForChar = 0;
for (let i = 0; i < s.length; i++) {
if (s[i].charCodeAt(0) === ch) {
count++;
} else {
if (count >= 3) maxForChar = Math.max(maxForChar, count);
count = 0;
}
}
if (count >= 3) maxForChar = Math.max(maxForChar, count);
if (maxForChar >= 3) maxLength = Math.max(maxLength, maxForChar);
}
return maxLength;
}
console.log(longestSpecialSubstring("abcaba")); // Output: 1#include <stdio.h>
#include <string.h>
int longestSpecialSubstring(char* s) {
int n = strlen(s);
int max_length = -1;
int current_count = 1;
int temp[26] = {0};
for (int i = 1; i <= n; ++i) {
if (i < n && s[i] == s[i - 1]) {
current_count++;
} else {
if (current_count >= 3) {
temp[s[i - 1] - 'a'] = current_count;
if (temp[s[i - 1] - 'a'] >= 3) {
max_length = (max_length < current_count) ? current_count : max_length;
}
}
current_count = 1;
}
}
return (max_length >= 3) ? max_length : -1;
}
int main() {
char s[] = "abcaba";
printf("%d\n", longestSpecialSubstring(s)); // Output: 1
return 0;
}using System;
public class Solution {
public static int LongestSpecialSubstring(string s) {
int max_length = -1;
for (char ch = 'a'; ch <= 'z'; ++ch) {
int count = 0, max_for_char = 0;
foreach (char c in s) {
if (c == ch) {
count++;
} else {
if (count >= 3) max_for_char = Math.Max(max_for_char, count);
count = 0;
}
}
if (count >= 3) max_for_char = Math.Max(max_for_char, count);
if (max_for_char >= 3) max_length = Math.Max(max_length, max_for_char);
}
return max_length;
}
public static void Main(string[] args) {
string s = "abcaba";
Console.WriteLine(LongestSpecialSubstring(s)); // Output: 1
}
}The Python technique cycles through each potential character 'a' to 'z', monitors repeats continuum within the string. Should the count encounter a valid length of at least three, it rescales the maximum possible length unless a potentially longer one emerges, iterating fully per character irrespective of presence.
Time Complexity: O(n), pointing to robust operation per each character's collection in O(n), with bounded alphabet range.
Space Complexity: O(1), aside from storing the string, you need solely constant additional space.
Approach 2: Approach 2: Sliding Window Technique with Dynamic Counting
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.
def longestSpecialSubstring(s):
max_length = -1
for char in 'abcdefghijklmnopqrstuvwxyz':
count, length_seen = 0, 0
i = 0
while i < len(s):
if s[i] == char:
count += 1
if count >= 3:
length_seen = count
i += 1
else:
max_length = max(max_length, length_seen)
i = i - count + 1
count = 0
length_seen = 0
max_length = max(max_length, length_seen)
return max_length >= 3 and max_length or -1
print(longestSpecialSubstring("abcaba")) # Output: 1public class Main {
public static int longestSpecialSubstring(String s) {
int max_length = -1;
for (char ch = 'a'; ch <= 'z'; ch++) {
int length_seen = 0, count = 0;
for (int i = 0; i < s.length();) {
if (s.charAt(i) == ch) {
count++;
if (count >= 3) {
length_seen = count;
}
i++;
} else {
max_length = Math.max(max_length, length_seen);
i = i - count + 1;
count = 0;
length_seen = 0;
}
}
max_length = Math.max(max_length, length_seen);
}
return max_length >= 3 ? max_length : -1;
}
public static void main(String[] args) {
String s = "abcaba";
System.out.println(longestSpecialSubstring(s)); // Output: 1
}
}#include <iostream>
#include <string>
int longestSpecialSubstring(std::string s) {
int max_length = -1;
for (char ch = 'a'; ch <= 'z'; ++ch) {
int count = 0, length_seen = 0;
for (int i = 0; i < s.length();) {
if (s[i] == ch) {
count++;
if (count >= 3) length_seen = count;
i++;
} else {
max_length = std::max(max_length, length_seen);
i = i + 1 - count + 1;
count = 0;
length_seen = 0;
}
}
max_length = std::max(max_length, length_seen);
}
return max_length >= 3 ? max_length : -1;
}
int main() {
std::string str = "abcaba";
std::cout << longestSpecialSubstring(str); // Output: 1
return 0;
}function longestSpecialSubstring(s) {
let maxLength = -1;
for (let ch = 97; ch <= 122; ch++) { // 'a' to 'z'
let count = 0;
let lengthSeen = 0;
let i = 0;
while (i < s.length) {
if (s[i].charCodeAt(0) === ch) {
count++;
if (count >= 3) {
lengthSeen = count;
}
i++;
} else {
maxLength = Math.max(maxLength, lengthSeen);
i = i + 1 - count + 1;
count = 0;
lengthSeen = 0;
}
}
maxLength = Math.max(maxLength, lengthSeen);
}
return maxLength >= 3 ? maxLength : -1;
}
console.log(longestSpecialSubstring("abcaba")); // Output: 1#include <stdio.h>
#include <string.h>
int longestSpecialSubstring(char* s) {
int n = strlen(s);
int max_length = -1;
for (char current = 'a'; current <= 'z'; ++current) {
int window_start = 0;
int length_seen = 0;
int count = 0;
while (window_start + count < n) {
if (s[window_start + count] == current) {
count++;
if (count >= 3) {
length_seen = count;
}
} else {
max_length = (max_length < length_seen) ? length_seen : max_length;
window_start += count + 1;
count = 0;
length_seen = 0;
}
}
max_length = (max_length < length_seen) ? length_seen : max_length;
}
return max_length >= 3 ? max_length : -1;
}
int main() {
char s[] = "abcaba";
printf("%d\n", longestSpecialSubstring(s)); // Output: 1
return 0;
}using System;
public class Solution {
public static int LongestSpecialSubstring(string s) {
int max_length = -1;
for (char ch = 'a'; ch <= 'z'; ++ch) {
int count = 0, length_seen = 0;
int i = 0;
while (i < s.Length) {
if (s[i] == ch) {
count++;
if (count >= 3) {
length_seen = count;
}
i++;
} else {
max_length = Math.Max(max_length, length_seen);
i = i + 1 - count + 1;
count = 0;
length_seen = 0;
}
}
max_length = Math.Max(max_length, length_seen);
}
return max_length >= 3 ? max_length : -1;
}
public static void Main(string[] args) {
string s = "abcaba";
Console.WriteLine(LongestSpecialSubstring(s)); // Output: 1
}
}The Python approach manifests essentially three-phase window handling: expansion, judgment call, and contraction alleviating via character reassessment recursively aligning longest captured potential amid both current and future loops, ultimately stationed with the maximum triple-compliant extract attempted in slices.
Time Complexity: O(n), frequently iterating but independently opted based on initialized datasets.
Space Complexity: O(1), applying manageable overhead beside string withholding.
Approach 3: Binary Search + Sliding Window Counting
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.
function maximumLength(s: string): number {
const n = s.length;
let [l, r] = [0, n];
const check = (x: number): boolean => {
const cnt: number[] = Array(26).fill(0);
for (let i = 0; i < n; ) {
let j = i + 1;
while (j < n && s[j] === s[i]) {
j++;
}
const k = s[i].charCodeAt(0) - 'a'.charCodeAt(0);
cnt[k] += Math.max(0, j - i - x + 1);
if (cnt[k] >= 3) {
return true;
}
i = j;
}
return false;
};
while (l < r) {
const mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l === 0 ? -1 : l;
}func maximumLength(s string) int {
n := len(s)
l, r := 0, n
check := func(x int) bool {
cnt := [26]int{}
for i := 0; i < n; {
j := i + 1
for j < n && s[j] == s[i] {
j++
}
k := s[i] - 'a'
cnt[k] += max(0, j-i-x+1)
if cnt[k] >= 3 {
return true
}
i = j
}
return false
}
for l < r {
mid := (l + r + 1) >> 1
if check(mid) {
l = mid
} else {
r = mid - 1
}
}
if l == 0 {
return -1
}
return l
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Linear Scan with Map Tracking | Time Complexity: O(n), pointing to robust operation per each character's collection in O(n), with bounded alphabet range. |
| Approach 2: Sliding Window Technique with Dynamic Counting | Time Complexity: O(n), frequently iterating but independently opted based on initialized datasets. |
| Binary Search + Sliding Window Counting | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Find Longest Special Substring That Occurs Thrice II easy or hard?
This problem is generally rated Medium because the brute-force idea is simple but inefficient. The challenge is recognizing that runs of identical characters can represent many substrings and leveraging that observation to reach an O(n) or O(n log n) solution.
Find Longest Special Substring That Occurs Thrice II Python/Java solution
Python and Java implementations usually scan the string to compute consecutive character runs and then aggregate counts using dictionaries or arrays. The logic runs in O(n) time and avoids expensive substring generation.
How to solve Find Longest Special Substring That Occurs Thrice II in O(n)?
Traverse the string and compress it into runs of identical characters. For each run of length L, it contributes L-k+1 substrings of length k. By aggregating contributions for each character and tracking when the count reaches three, you can determine the maximum valid substring length in linear time.
What is the best approach for Find Longest Special Substring That Occurs Thrice II?
The most efficient method is scanning the string to collect lengths of consecutive character runs and aggregating how many substrings each run can generate. This linear scan avoids generating substrings explicitly and computes the maximum valid length in O(n) time.
Is Find Longest Special Substring That Occurs Thrice II asked at Google/Amazon/Meta?
Substring counting and run-length based string problems are common in interviews at companies like Google, Amazon, and Meta. Variations of this problem test understanding of sliding windows, substring counting, and optimization from brute force to linear scans.
What data structure is used in Find Longest Special Substring That Occurs Thrice II?
Typical solutions use hash maps or fixed-size arrays to track counts of substring contributions for each character. Run-length arrays and counters are used alongside techniques such as sliding window or binary search.
What is the time complexity of Find Longest Special Substring That Occurs Thrice II?
The optimal run-length tracking solution runs in O(n) time because the string is scanned once to build consecutive character segments. Space complexity is typically O(n) in the worst case if many short runs are stored.