3090. 每个字符最多出现两次的最长子字符串

题目描述

给你一个字符串 s ，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的最大长度。

示例 1：

输入： s = "bcbbbcba"

输出： 4

解释：

以下子字符串长度为 4，并且每个字符最多出现两次："bcbbbcba"。

示例 2：

输入： s = "aaaa"

输出： 2

解释：

以下子字符串长度为 2，并且每个字符最多出现两次："aaaa"。

提示：

2 <= s.length <= 100
s 仅由小写英文字母组成。

解法

方法一：双指针

思考

子串中每个字符至多出现两次。\(n \le 100\)，枚举子串可行，但约束是典型的滑动窗口。

右端纳入字符后，若某计数超过 \(2\)，左端必须右移直到该计数回到 \(2\)。窗口合法时更新最大长度。

哈希计数配合双指针一遍扫描。

我们用两个指针 \(l\) 和 \(r\) 来维护一个滑动窗口，用一个数组 \(cnt\) 来记录窗口中每个字符的出现次数。

每一次，我们将指针 \(r\) 对应的字符 \(c\) 加入窗口，然后判断 \(cnt[c]\) 是否大于 \(2\)，如果大于 \(2\)，则将指针 \(l\) 循环右移，直到 \(cnt[c]\) 小于等于 \(2\)。此时，我们更新答案 \(ans = \max(ans, r - l + 1)\)。

最终，我们返回答案 \(ans\)。

时间复杂度 \(O(n)\)，其中 \(n\) 为字符串 \(s\) 的长度。空间复杂度 \(O(|\Sigma|)\)，其中 \(\Sigma\) 为字符集，本题中 \(\Sigma = 26\)。

Python3JavaC++GoTypeScriptRust

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        ans = l = 0
        cnt = defaultdict(int)
        for r, c in enumerate(s):
            cnt[c] += 1
            while cnt[c] > 2:
                cnt[s[l]] -= 1
                l += 1
            ans = max(ans, r - l + 1)
        return ans

class Solution {
    public int maximumLengthSubstring(String s) {
        int ans = 0;
        int[] cnt = new int[26];
        for (int l = 0, r = 0; r < s.length(); ++r) {
            int idx = s.charAt(r) - 'a';
            ++cnt[idx];
            while (cnt[idx] > 2) {
                --cnt[s.charAt(l++) - 'a'];
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

class Solution {
public:
    int maximumLengthSubstring(string s) {
        int ans = 0;
        int cnt[26]{};
        for (int l = 0, r = 0; r < s.size(); ++r) {
            int idx = s[r] - 'a';
            ++cnt[idx];
            while (cnt[idx] > 2) {
                --cnt[s[l++] - 'a'];
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

func maximumLengthSubstring(s string) (ans int) {
    l := 0
    cnt := [26]int{}
    for r, c := range s {
        idx := int(c - 'a')
        cnt[idx]++
        for cnt[idx] > 2 {
            cnt[s[l]-'a']--
            l++
        }
        ans = max(ans, r-l+1)
    }
    return
}

function maximumLengthSubstring(s: string): number {
    let ans = 0;
    const cnt: number[] = Array(26).fill(0);
    for (let l = 0, r = 0; r < s.length; ++r) {
        const idx = s[r].charCodeAt(0) - 97;
        ++cnt[idx];
        while (cnt[idx] > 2) {
            --cnt[s[l++].charCodeAt(0) - 97];
        }
        ans = Math.max(ans, r - l + 1);
    }
    return ans;
}

impl Solution {
    pub fn maximum_length_substring(s: String) -> i32 {
        let mut cnt = [0; 26];
        let mut ans = 0;
        let mut l = 0;
        let s = s.as_bytes();

        for (r, &c) in s.iter().enumerate() {
            let i = (c - b'a') as usize;
            cnt[i] += 1;

            while cnt[i] > 2 {
                cnt[(s[l] - b'a') as usize] -= 1;
                l += 1;
            }

            ans = ans.max((r - l + 1) as i32);
        }

        ans
    }
}

3090. 每个字符最多出现两次的最长子字符串

题目描述

解法

方法一：双指针

评论