leetcode340. 至多包含 K 个不同字符的最长子串

太过爱你忘了你带给我的痛 2023-07-02 12:27 2阅读 0赞

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

示例 1:

输入: s = "eceba", k = 2  
输出: 3  
解释: 则 T 为 "ece"，所以长度为 3。  
示例 2:

输入: s = "aa", k = 1  
输出: 2  
解释: 则 T 为 "aa"，所以长度为 2。

思路：双指针，指针中间的是可能的答案。符合要求右指针向右扩，否则更新答案，左指针往右缩。

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

class Solution {
      public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int n = s.length();
        if (n < k+1) return n;
     
        int left = 0;
        int right = 0;
        //K-V：K是对应字符，V是最后一次出现的位置。
        HashMap<Character, Integer> hashmap = new HashMap<Character, Integer>();
     
        int max_len = 0;
     
        while (right < n) {
            //符合要求就继续向右扩
            if (hashmap.size() < k+1){
                hashmap.put(s.charAt(right), right++);
            }
            if (hashmap.size() == k+1) {
                int index = Collections.min(hashmap.values());
                hashmap.remove(s.charAt(index));
                left = index + 1;
            }
          max_len = Math.max(max_len, right - left);
        }
        return max_len;
      }
    }

[leetcode159.]: https://blog.csdn.net/hebtu666/article/details/104107625

发表评论取消回复

表情：

评论列表（有 0 条评论，2人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode340. 至多包含 K 个不同字符的最长子串

给定一个字符串 s ，找出至多包含 k 个不同字符的最长子串 T。示例 1: 输入: s = "eceba", k = 2 输出: 3 解释: 则 T 为 "

太过爱你忘了你带给我的痛/ 2023年07月02日 12:27/ 0 赞/ 3 阅读

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

给定一个字符串 s ，找出至多包含两个不同字符的最长子串 t 。示例 1: 输入: "eceba" 输出: 3 解释: t 是 "ece"，长度为3。示

超、凢脫俗/ 2023年07月02日 11:23/ 0 赞/ 12 阅读

相关 LeetCode--无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例 1: 输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串

分手后的思念是犯贱/ 2023年01月07日 05:59/ 0 赞/ 150 阅读

相关 leetcode-340 Longest Substring with at most k-distinct characters（至多包含 K 个不同字符的最长子串）

题目描述给定一个字符串 s ，找出至多包含 k 个不同字符的最长子串 T。示例 1: 输入: s = "eceba", k = 2

绝地灬酷狼/ 2022年12月26日 11:15/ 0 赞/ 102 阅读

相关 LeetCode395. 至少有K个重复字符的最长子串

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串，要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。示例 1：输入：s = “aaab

今天药忘吃喽~/ 2022年11月03日 10:45/ 0 赞/ 113 阅读

相关 LeetCode 395. 至少有K个重复字符的最长子串

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

我会带着你远行/ 2022年10月27日 06:21/ 0 赞/ 96 阅读

相关 leetcode 395. 至少有 K 个重复字符的最长子串

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串，要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。示例 1：输入：s = "aaab

叁歲伎倆/ 2022年09月03日 12:16/ 0 赞/ 83 阅读

相关 [LeetCode] 无重复字符的最长子串

无重复字符的最长子串英文描述 Given a string, find the length of the longest substring without r

今天药忘吃喽~/ 2022年05月28日 09:38/ 0 赞/ 230 阅读

相关 LeetCode 无重复字符的最长子串

给定一个字符串，找出不含有重复字符的最长子串的长度。示例 1: 输入: “abcabcbb” 输出: 3 解释: 无重复字符的最长子串是 “abc”，其长度为 3

ゝ一纸荒年。/ 2022年05月15日 06:43/ 0 赞/ 216 阅读

相关 leetcode 无重复字符的最长子串

问题描述给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。 > 输入: “abcabcbb” > 输出: 3 > 解释: 因为无重复字符的最长子

青旅半醒/ 2022年03月17日 13:50/ 0 赞/ 242 阅读