# 2981. Find Longest Special Substring That Occurs Thrice I

## Description

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 <= 50
• s consists of only lowercase English letters.

## Solutions

Solution 1: 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$.

• class Solution {
private String s;
private int n;

public int maximumLength(String s) {
this.s = s;
n = s.length();
int l = 0, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l == 0 ? -1 : l;
}

private boolean check(int x) {
int[] cnt = new int[26];
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && s.charAt(j) == s.charAt(i)) {
j++;
}
int k = s.charAt(i) - 'a';
cnt[k] += Math.max(0, j - i - x + 1);
if (cnt[k] >= 3) {
return true;
}
i = j;
}
return false;
}
}

• class Solution {
public:
int maximumLength(string s) {
int n = s.size();
int l = 0, r = n;
auto check = [&](int x) {
int cnt[26]{};
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && s[j] == s[i]) {
++j;
}
int k = s[i] - 'a';
cnt[k] += max(0, j - i - x + 1);
if (cnt[k] >= 3) {
return true;
}
i = j;
}
return false;
};
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l == 0 ? -1 : l;
}
};

• class Solution:
def maximumLength(self, s: str) -> int:
def check(x: int) -> bool:
cnt = defaultdict(int)
i = 0
while i < n:
j = i + 1
while j < n and s[j] == s[i]:
j += 1
cnt[s[i]] += max(0, j - i - x + 1)
i = j
return max(cnt.values()) >= 3

n = len(s)
l, r = 0, n
while l < r:
mid = (l + r + 1) >> 1
if check(mid):
l = mid
else:
r = mid - 1
return -1 if l == 0 else 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
}

• 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;
}