class Solution {
public:
int maximumLength(string s) {
}
};
2981. 找出出现至少三次的最长特殊子字符串 I
给你一个仅由小写英文字母组成的字符串 s 。
如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。
返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。
子字符串 是字符串中的一个连续 非空 字符序列。
示例 1：
输入：s = "aaaa" 输出：2 解释：出现三次的最长特殊子字符串是 "aa" ：子字符串 "aaaa"、"aaaa" 和 "aaaa"。 可以证明最大长度是 2 。
示例 2：
输入：s = "abcdef" 输出：-1 解释：不存在出现至少三次的特殊子字符串。因此返回 -1 。
示例 3：
输入：s = "abcaba" 输出：1 解释：出现三次的最长特殊子字符串是 "a" ：子字符串 "abcaba"、"abcaba" 和 "abcaba"。 可以证明最大长度是 1 。
提示：
3 <= s.length <= 50s 仅由小写英文字母组成。原站题解
rust 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2024-05-29 09:23:37
impl Solution {
pub fn maximum_length(s: String) -> i32 {
let mut groups = vec![vec![]; 26];
let s = s.as_bytes();
let mut cnt = 0;
for (i, &c) in s.iter().enumerate() {
cnt += 1;
if i + 1 == s.len() || c != s[i + 1] {
groups[(c - b'a') as usize].push(cnt); // 统计连续字符长度
cnt = 0;
}
}
let mut ans = 0;
for a in groups.iter_mut() {
if a.is_empty() {
continue;
}
a.sort_unstable_by(|x, y| y.cmp(x));
a.push(0);
a.push(0); // 假设还有两个空串
ans = ans.max(a[0] - 2).max(a[1].min(a[0] - 1)).max(a[2]);
}
if ans > 0 { ans } else { -1 }
}
}
javascript 解法, 执行用时: 88 ms, 内存消耗: 54.7 MB, 提交时间: 2024-05-29 09:23:20
/**
* @param {string} s
* @return {number}
*/
var maximumLength = function(s) {
const n = s.length;
const groups = Array.from({ length: 26 }, () => []);
let cnt = 0;
for (let i = 0; i < n; i++) {
cnt++;
if (i + 1 === n || s[i] !== s[i + 1]) {
groups[s[i].charCodeAt(0) - 'a'.charCodeAt(0)].push(cnt); // 统计连续字符长度
cnt = 0;
}
}
let ans = 0;
for (let a of groups) {
if (a.length === 0) {
continue;
}
a.sort((x, y) => y - x);
a.push(0);
a.push(0); // 假设还有两个空串
ans = Math.max(ans, a[0] - 2, Math.min(a[0] - 1, a[1]), a[2]);
}
return ans ? ans : -1;
};
golang 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2024-01-01 19:24:16
func maximumLength(s string) int {
groups := [26][]int{}
cnt := 0
for i := range s {
cnt++
if i == len(s)-1 || s[i] != s[i+1] {
groups[s[i]-'a'] = append(groups[s[i]-'a'], cnt) // 统计连续字符长度
cnt = 0
}
}
ans := 0
for _, a := range groups {
if len(a) == 0 {
continue
}
slices.SortFunc(a, func(a, b int) int { return b - a })
a = append(a, 0, 0) // 假设还有两个空串
ans = max(ans, a[0]-2, min(a[0]-1, a[1]), a[2])
}
if ans == 0 {
return -1
}
return ans
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 7.5 MB, 提交时间: 2024-01-01 19:24:03
class Solution {
public:
int maximumLength(string s) {
vector<int> groups[26];
int cnt = 0, n = s.length();
for (int i = 0; i < n; i++) {
cnt++;
if (i + 1 == n || s[i] != s[i + 1]) {
groups[s[i] - 'a'].push_back(cnt); // 统计连续字符长度
cnt = 0;
}
}
int ans = 0;
for (auto &a: groups) {
if (a.empty()) continue;
sort(a.rbegin(), a.rend());
a.push_back(0);
a.push_back(0); // 假设还有两个空串
ans = max({ans, a[0] - 2, min(a[0] - 1, a[1]), a[2]});
}
return ans ? ans : -1;
}
};
java 解法, 执行用时: 4 ms, 内存消耗: 42.3 MB, 提交时间: 2024-01-01 19:23:50
public class Solution {
public int maximumLength(String S) {
char[] s = S.toCharArray();
List<Integer>[] groups = new ArrayList[26];
Arrays.setAll(groups, i -> new ArrayList<>());
int cnt = 0;
for (int i = 0; i < s.length; i++) {
cnt++;
if (i == s.length - 1 || s[i] != s[i + 1]) {
groups[s[i] - 'a'].add(cnt); // 统计连续字符长度
cnt = 0;
}
}
int ans = 0;
for (List<Integer> a : groups) {
if (a.isEmpty()) continue;
a.sort(Collections.reverseOrder());
a.add(0);
a.add(0); // 假设还有两个空串
ans = Math.max(ans, Math.max(a.get(0) - 2, Math.max(Math.min(a.get(0) - 1, a.get(1)), a.get(2))));
}
return ans > 0 ? ans : -1;
}
}
python3 解法, 执行用时: 44 ms, 内存消耗: 17.1 MB, 提交时间: 2024-01-01 19:23:43
class Solution:
def maximumLength(self, s: str) -> int:
groups = defaultdict(list)
cnt = 0
for i, ch in enumerate(s):
cnt += 1
if i == len(s) - 1 or ch != s[i + 1]:
groups[ch].append(cnt) # 统计连续字符长度
cnt = 0
ans = 0
for a in groups.values():
a.sort(reverse=True)
a.extend([0, 0]) # 假设还有两个空串
ans = max(ans, a[0] - 2, min(a[0] - 1, a[1]), a[2])
return ans if ans else -1