侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 26 条评论

目 录CONTENT

文章目录

【滑动窗口】至多包含两个不同字符的最长子串

GabrielxD
2022-10-18 / 0 评论 / 0 点赞 / 251 阅读 / 263 字
温馨提示:
本文最后更新于 2022-11-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

159. 至多包含两个不同字符的最长子串


给你一个字符串 s ,请你找出 至多 包含 两个不同字符 的最长子串,并返回该子串的长度。

示例 1:

输入:s = "eceba"
输出:3
解释:满足题目要求的子串是 "ece" ,长度为 3 。

示例 2:

输入:s = "ccaabbb"
输出:5
解释:满足题目要求的子串是 "aabbb" ,长度为 5 。

提示:

  • 1 <= s.length <= 10^5
  • s 由英文字母组成

解题

方法一:滑动窗口

思路

【哈希表, 滑动窗口】无重复字符的最长子串差不多。
滑动窗口模板秒了。

代码

class Solution {
    static final int HASH_LEN = 'z' + 1;

    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int[] window = new int[HASH_LEN];
        char[] chs = s.toCharArray();
        int n = chs.length;
        int left = 0, right = 0;
        int maxLen = 0, diffCnt = 0;
        while (right < n) {
            if (++window[chs[right++]] == 1) ++diffCnt;
            while (diffCnt == 3) {
                if (--window[chs[left++]] == 0) --diffCnt;
            }
            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }
}
0

评论区