同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
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.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:
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
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;
}
};
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;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。