Find Longest Special Substring That Occurs Thrice I
Problem
A string is special if it is made of a single repeated character (like "a", "zz", or "ddd"). Given a lowercase string s, return the length of the longest special substring that occurs at least three times. If no special substring occurs at least thrice, return -1.
s = "aaaa"2aaaa, aaaa, and aaaa. Length 3 only appears twice, so 2 is the best.def maximumLength(s):
n = len(s)
# count[(ch, L)] = how many special substrings of char ch
# and length L exist across the whole string.
count = {}
i = 0
while i < n:
# find the maximal run of equal characters [i, j)
j = i
while j < n and s[j] == s[i]:
j += 1
run = j - i
# a run of length `run` contains (run - L + 1) substrings
# of length L for every 1 <= L <= run
for L in range(1, run + 1):
key = (s[i], L)
count[key] = count.get(key, 0) + (run - L + 1)
i = j
ans = -1
for (ch, L), c in count.items():
if c >= 3: # occurs at least thrice
ans = max(ans, L)
return ansfunction maximumLength(s) {
const n = s.length;
// count[ch + "," + L] = number of special substrings of
// character ch with length L across the whole string.
const count = new Map();
let i = 0;
while (i < n) {
// find the maximal run of equal characters [i, j)
let j = i;
while (j < n && s[j] === s[i]) j++;
const run = j - i;
// a run of length `run` yields (run - L + 1) substrings
// of length L for every 1 <= L <= run
for (let L = 1; L <= run; L++) {
const key = s[i] + "," + L;
count.set(key, (count.get(key) || 0) + (run - L + 1));
}
i = j;
}
let ans = -1;
for (const [key, c] of count) {
if (c >= 3) { // occurs at least thrice
const L = parseInt(key.split(",")[1], 10);
ans = Math.max(ans, L);
}
}
return ans;
}int maximumLength(String s) {
int n = s.length();
// count.get(ch * 100 + L) = number of special substrings of
// character ch with length L across the whole string.
Map<Integer, Integer> count = new HashMap<>();
int i = 0;
while (i < n) {
// find the maximal run of equal characters [i, j)
int j = i;
while (j < n && s.charAt(j) == s.charAt(i)) j++;
int run = j - i;
// a run of length `run` yields (run - L + 1) substrings
// of length L for every 1 <= L <= run
for (int L = 1; L <= run; L++) {
int key = s.charAt(i) * 100 + L;
count.merge(key, run - L + 1, Integer::sum);
}
i = j;
}
int ans = -1;
for (Map.Entry<Integer, Integer> e : count.entrySet()) {
if (e.getValue() >= 3) // occurs at least thrice
ans = Math.max(ans, e.getKey() % 100);
}
return ans;
}int maximumLength(string s) {
int n = s.size();
// count[{ch, L}] = number of special substrings of character
// ch with length L across the whole string.
map<pair<char,int>, int> count;
int i = 0;
while (i < n) {
// find the maximal run of equal characters [i, j)
int j = i;
while (j < n && s[j] == s[i]) j++;
int run = j - i;
// a run of length `run` yields (run - L + 1) substrings
// of length L for every 1 <= L <= run
for (int L = 1; L <= run; L++)
count[{s[i], L}] += run - L + 1;
i = j;
}
int ans = -1;
for (auto& [key, c] : count)
if (c >= 3) // occurs at least thrice
ans = max(ans, key.second);
return ans;
}Explanation
A special substring is just a block of one repeated letter, so every special substring lives entirely inside one maximal run of equal characters. That observation lets us avoid checking arbitrary substrings.
We scan s left to right, slicing it into maximal runs. For a run of length run of character ch, the number of length-L windows it contains is run − L + 1 (for every 1 ≤ L ≤ run). Those windows are exactly the occurrences of the special string "ch repeated L times" contributed by this run.
We accumulate these counts into a map keyed by (ch, L). Different runs of the same character add together, because the same special string can appear in more than one run.
Finally we look for the largest length L whose total occurrence count is at least 3. If no key reaches three occurrences, the answer is -1. Because s.length ≤ 50 the counting is tiny and exact.
Example: s = "aaaa" is a single run of length 4. Length 1 occurs 4 times, length 2 occurs 3 times, length 3 occurs twice, length 4 once. The longest length reaching three occurrences is 2.