给定一个长度为 n 的字符串 s ,找出最多包含 k 种不同字符的最长连续子串的长度。
数据范围: , 字符串中仅包含小写英文字母
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; }
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; } }