跳转至

3773. 最大等长连续字符组 🔒

题目描述

给定一个由小写英文字母组成的字符串 s。

s 中的一个 连续字符组 是一个由无法再扩展的 相同 字符组成的 子串。例如，"hello" 中的连续字符组是 "h"，"e"，"ll" 和 "o"。

你可以 选择 s 中 相同 长度的字符组。

返回一个整数，表示你可以在 s 中选择的最多连续字符组。

 

示例 1：

输入：s = "hello"

输出：3

解释：

s 中的连续字符组是 "h"，"e"，"ll" 和 "o"。你可以选择 "h"，"e" 和 "o" 因为它们有相同的长度 1。

示例 2：

输入：s = "aaabaaa"

输出：2

解释：

s 中的连续字符组是 "aaa"，"b" 和 "aaa"。你可以选择 "aaa" 和 "aaa" 因为它们有相同的长度 3。

 

提示：

  • 1 <= s.length <= 105
  • s 只包含小写英文字母。

解法

方法一：哈希表

我们可以用一个哈希表 \(\textit{cnt}\) 来记录每个连续字符组长度出现的次数。遍历字符串 \(s\)，对于每个连续字符组，计算其长度 \(m\)，并将 \(\textit{cnt}[m]\) 加 \(1\)。最后，答案即为 \(\textit{cnt}\) 中的最大值。

时间复杂度

1
2
3
4
5
6
class Solution:
    def maxSameLengthRuns(self, s: str) -> int:
        cnt = Counter()
        for _, g in groupby(s):
            cnt[len(list(g))] += 1
        return max(cnt.values())

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int maxSameLengthRuns(String s) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int ans = 0;
        int n = s.length();
        for (int i = 0; i < n;) {
            int j = i + 1;
            while (j < n && s.charAt(j) == s.charAt(i)) {
                ++j;
            }
            int m = j - i;
            ans = Math.max(ans, cnt.merge(m, 1, Integer::sum));
            i = j;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxSameLengthRuns(string s) {
        unordered_map<int, int> cnt;
        int ans = 0;
        int n = s.size();
        for (int i = 0; i < n;) {
            int j = i + 1;
            while (j < n && s[j] == s[i]) {
                ++j;
            }
            int m = j - i;
            ans = max(ans, ++cnt[m]);
            i = j;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func maxSameLengthRuns(s string) (ans int) {
    cnt := map[int]int{}
    n := len(s)
    for i := 0; i < n; {
        j := i + 1
        for j < n && s[j] == s[i] {
            j++
        }
        m := j - i
        cnt[m]++
        ans = max(ans, cnt[m])
        i = j
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function maxSameLengthRuns(s: string): number {
    const cnt: Record<number, number> = {};
    const n = s.length;
    let ans = 0;
    for (let i = 0; i < n; ) {
        let j = i + 1;
        while (j < n && s[j] === s[i]) {
            ++j;
        }
        const m = j - i;
        cnt[m] = (cnt[m] || 0) + 1;
        ans = Math.max(ans, cnt[m]);
        i = j;
    }
    return ans;
}

评论