算法 1.8.3 至多包含 K 个不同字符的最长子串【leetc

题目描述

给定一个字符串 s ，找出 至多 包含 k 个不同字符的最长子串 T。

示例 1:
  输入: s = "eceba", k = 2
  输出: 3

解释:
  T 为 "ece"，所以长度为 3。

示例 2:
  输入: s = "aa", k = 1
  输出: 2

解释:
  T 为 "aa"，所以长度为 2。

数据结构

• 指针、哈希表

算法思维

• 遍历、双指针、哈希（散列）、滑动窗口

解题要点

• “范围问题” 或 “同步变化” ==> 双指针
• “快速查找” 或 “重复匹配” ==> 哈希表
• “最长/最短长度” 且 “需要长度而不是内容” ==> “滑动窗口”

解题思路

---

一. Comprehend 理解题意

• 要求是子串，不是子序列
• 子串最多由两个不同字符 按任意数量 排列组合而成
• 不要求记录子串，只需要记录长度
  
  

二. Choose 选择数据结构与算法

双指针 + 哈希表 + 滑动窗口 解法

• 数据结构：指针、哈希表
• 算法思维：遍历、双指针、哈希（散列）、滑动窗口

解题思路

1. 声明一个哈希表 new int[128]
     被哈希的对象为 ASCII 字符，因此只需要一个 128 的数组
     无需哈希函数，索引即为字符的 ASCII 码，哈希表存放该字符在子串中出现的个数
2. 声明一个整形变量 count 存放“不同字符”的个数，按照题目要求，应有 count <= k
3. 左右两个指针组成一个“滑动窗口”，遍历整个字符串
     判断右指针字符是否是“新字符”
       如果是新字符，不同字符数 count++
     右指针在哈希表中相应位置的数据 +1，表示右指针字符在子串中出现的次数 +1
     右指针右移，滑动窗口长度 +1
     判断不同字符数 count 是否大于 k，如果大于 k：
       左指针在哈希表中相应位置的数据 -1，表示左指针字符在子串中出现的次数 -1
       判断左指针在哈希表中相应位置的数据是否 == 0
         如果为 0，说明当前删除的左指针字符是子串中的“最后一个”，不同字符数 count--
       左指针右移，滑动窗口长度 -1
4. 最终返回滑动窗口的长度：右指针索引 - 左指针索引

边界问题

• 右指针（right）领先左指针（left），因此边界条件为：right < s.length()

细节问题

• 关于滑动窗口最终的长度：由于循环结束前右指针先右移了一步，右指针索引已经为字符数组索引 +1，因此 return right - left，最终结果不用再 +1
  
  

三. Code 编码实现基本解法

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {

        int len = s.length();
        int count = 0; //不同字符的个数

        //1.定义一个哈希表和两个指针
        int[] map = new int[128];
        int left = 0, right = 0;

        //2.遍历字符串
        while(right < len){
            //3.如果当前是新字符，count++
            if (map[s.charAt(right++)]++ == 0){
                count++;
            }
            //4.如果不同字符个数超过要求，就删除左指针字符
            if (count > k){
                //5.如果删除之后 map 中为 0，则count--
                if (--map[s.charAt(left++)] == 0){
                    count--;
                }
            }
        }

        //6.最终返回浮动窗口的长度
        return right - left;
    }
}

执行耗时：5 ms，击败了 83.75% 的Java用户
内存消耗：38.6 MB，击败了 68.76% 的Java用户
时间复杂度：O(n) -- 一次链表的遍历 O(n)，查询哈希表 O(1)
空间复杂度：O(1) -- 一个哈希表 O(1)，两个指针 O(1)，两个整数变量 O(1)

四. Consider 思考更优解

== 暂无 ==

五. Code 编码实现最优解

== 暂无 ==

六. Change 变形与延伸

=== 待续 ===