至多包含K种字符的子串

[编程题]至多包含K种字符的子串

热度指数：2447 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 n 的字符串 s ，找出最多包含 k 种不同字符的最长连续子串的长度。

数据范围： $1 \le n \le 10^5 \$ ，字符串中仅包含小写英文字母

示例1

输入

"abcck",1

输出

示例2

输入

"abcck",2

输出

说明

最后三个字符 “cck” 组成最长子串

算法知识视频讲解

Java

牛客294317031号

public int longestSubstring(String s, int k) {//滑动窗口 + 哈希表
    StringBuilder sb = new StringBuilder(s);
    int n = sb.length();
    if (n <= k) return n;
    Map<Character, Integer> map = new HashMap<>();
    int res = 0;
    for (int r = 0, l = 0; r < n; r++) {
        char c = sb.charAt(r);
        map.put(c, map.getOrDefault(c, 0) + 1);
        while (map.size() > k) {
            c = sb.charAt(l);
            map.put(c, map.getOrDefault(c, 0) - 1);
            if (map.get(c) == 0) map.remove(c);
            l++;
        }
        res = Math.max(res, r - l + 1);
    }
    return res;
}

发表于 2024-05-07 09:26:53 回复(0)

Java

弱渣求上岸

import java.util.*;

public class Solution {
    public int longestSubstring (String s, int k) {
        if(k > s.length() || s == null || s.length() == 0){
            return 0;
        }
        int res = 0;
        int l = 0;
        int count = 0;
        int[] arr = new int[26];
        for(int r = 0; r < s.length(); r++){
            char c = s.charAt(r);
            if(arr[c - 'a'] == 0){
                count++;
            }
            arr[c - 'a']++;
            while(count > k){
                if(arr[s.charAt(l) - 'a'] == 1){
                    count--;
                }
                arr[s.charAt(l) - 'a']--;
                l++;
            }
            res = Math.max(res, r - l + 1);
        }
        return res;
    }
}

leetcode 159原题

java版滑动窗口

发表于 2022-05-27 10:06:01 回复(1)