Welcome to Subscribe On Youtube
2982. Find Longest Special Substring That Occurs Thrice II
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 <= 5 * 105sconsists 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; }