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

Categories:

题目描述
思路分析
1. 解法一：滑动窗口（推荐）
相似题目

题目描述

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

思路分析

解法一：滑动窗口（推荐）

核心思路：

用左右指针维护窗口，统计窗口内字符出现次数。

当不同字符数超过 2 时，不断移动左指针缩小窗口。

每次窗口合法时更新最大长度。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(1)，字符集大小固定。

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int[] cnt = new int[128];
        int left = 0;
        int distinct = 0;
        int res = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (cnt[c] == 0) {
                distinct++;
            }
            cnt[c]++;

            // 缩小窗口直到只剩两种字符
            while (distinct > 2) {
                char lc = s.charAt(left);
                cnt[lc]--;
                if (cnt[lc] == 0) {
                    distinct--;
                }
                left++;
            }

            res = Math.max(res, right - left + 1);
        }

        return res;
    }
}

func lengthOfLongestSubstringTwoDistinct(s string) int {
    cnt := make([]int, 128)
    left := 0
    distinct := 0
    res := 0

    for right := 0; right < len(s); right++ {
        c := s[right]
        if cnt[c] == 0 {
            distinct++
        }
        cnt[c]++

        // 缩小窗口直到只剩两种字符
        for distinct > 2 {
            lc := s[left]
            cnt[lc]--
            if cnt[lc] == 0 {
                distinct--
            }
            left++
        }

        if right-left+1 > res {
            res = right - left + 1
        }
    }

    return res
}

相似题目

题目	难度	考察点
340. 至多包含 K 个不同字符的最长子串	困难	滑动窗口
3. 无重复字符的最长子串	中等	滑动窗口
76. 最小覆盖子串	困难	滑动窗口
438. 找到字符串中所有字母异位词	中等	滑动窗口
424. 替换后的最长重复字符	中等	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/88184672