Find Longest Special Substring That Occurs Thrice I Solution
Find Longest Special Substring That Occurs Thrice I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find Longest Special Substring That Occurs Thrice I is a medium coding problem on strings, hash table and binary search, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Binary Search, Counting, Sliding Window
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s of lowercase letters.
A string is special if every character in it is the same — "ddd", "z" and "ff" are special, "abc" and "ccd" are not.
Return the length of the longest special substring of s that occurs at least three times (occurrences may overlap), or -1 if no special substring occurs three times.
Example 1
Input: s = "aaaa"
Output: 2
Explanation: "aa" starts at indices 0, 1 and 2. "aaa" occurs only twice.
Example 2
Input: s = "abcdef"
Output: -1
Explanation: Every special substring is a single letter that occurs once.
Example 3
Input: s = "abcaba"
Output: 1
Explanation: "a" occurs at indices 0, 3 and 5.
Constraints
3 <= s.length <= 50s consists only of lowercase English letters
Hints for Find Longest Special Substring That Occurs Thrice I
Hint 1
A special substring lives entirely inside one maximal run of a single repeated letter.
Hint 2
A run of letter
cwith lengthLcontains the special string of lengthlexactlyL - l + 1times (forl <= L).Hint 3
For every letter and every length, add those counts over all runs, and keep the largest length whose total reaches 3.
How to solve Find Longest Special Substring That Occurs Thrice I
Split s into maximal runs of one letter. Every occurrence of a special substring sits inside one run, and a run of length L contributes L - l + 1 occurrences of the length-l string of its letter. Summing those per (letter, length) gives every occurrence count directly.
Approach
- Walk
sand cut it into maximal runs; for a run of lettercand lengthL, addL - l + 1tocount[c][l]for everylfrom 1 toL. - Scan all
(c, l)withcount[c][l] >= 3and keep the largestl. - Return it, or
-1if there is none.
Why it works
Two different runs of the same letter are separated by another letter, so no occurrence spans two runs, and inside a run every window of length l is an occurrence. The sum therefore counts every occurrence exactly once.
Complexity
- Time —
O(n^2) at worst (the sum of the squared run lengths) - Space —
O(26 * n)
Pitfalls
- Occurrences may overlap: "aaaa" contains "aa" three times.
- Runs of the same letter in different places all add to the same counter — in "aabaab" the two runs of
atogether give "a" four times.
Reference solution
Python
def maximumLength(s: str) -> int:
n = len(s)
count = [[0] * (n + 2) for _ in range(26)]
i = 0
while i < n:
j = i
while j < n and s[j] == s[i]:
j += 1
run = j - i
c = ord(s[i]) - 97
for l in range(1, run + 1):
count[c][l] += run - l + 1
i = j
best = -1
for c in range(26):
for l in range(1, n + 1):
if count[c][l] >= 3 and l > best:
best = l
return bestJava
public static int maximumLength(String s) {
int n = s.length();
int[][] count = new int[26][n + 2];
int i = 0;
while (i < n) {
int j = i;
while (j < n && s.charAt(j) == s.charAt(i)) j++;
int run = j - i, c = s.charAt(i) - 'a';
for (int l = 1; l <= run; l++) count[c][l] += run - l + 1;
i = j;
}
int best = -1;
for (int c = 0; c < 26; c++)
for (int l = 1; l <= n; l++)
if (count[c][l] >= 3 && l > best) best = l;
return best;
}C++
int maximumLength(string s) {
int n = s.size();
vector<vector<int>> count(26, vector<int>(n + 2, 0));
int i = 0;
while (i < n) {
int j = i;
while (j < n && s[j] == s[i]) j++;
int run = j - i, c = s[i] - 'a';
for (int l = 1; l <= run; l++) count[c][l] += run - l + 1;
i = j;
}
int best = -1;
for (int c = 0; c < 26; c++)
for (int l = 1; l <= n; l++)
if (count[c][l] >= 3 && l > best) best = l;
return best;
}JavaScript
var maximumLength = function(s) {
var n = s.length;
var count = [];
for (var c = 0; c < 26; c++) {
count.push(new Array(n + 2).fill(0));
}
var i = 0;
while (i < n) {
var j = i;
while (j < n && s[j] === s[i]) j++;
var run = j - i, ch = s.charCodeAt(i) - 97;
for (var l = 1; l <= run; l++) count[ch][l] += run - l + 1;
i = j;
}
var best = -1;
for (var c2 = 0; c2 < 26; c2++) {
for (var l2 = 1; l2 <= n; l2++) {
if (count[c2][l2] >= 3 && l2 > best) best = l2;
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets