Sliding Window - 340. Longest Substring with At Most K Distinct Characters

ppxai

发布于 2020-09-23 17:18:14

53100

代码可运行

文章被收录于专栏：皮皮星球皮皮星球

运行总次数：0

代码可运行

Longest Substring with At Most K Distinct Characters

Given a string S, find the length of the longest substring T that contains at most k distinct characters.

Example 1:

Input: S = "eceba" and k = 3 Output: 4 Explanation: T = "eceb"

Example 2:

Input: S = "WORLD" and k = 4 Output: 4 Explanation: T = "WORL" or "ORLD"

思路：

题目意思是说给定一个k，找出一个连续子串，子串里面最多只允许出现k个不同的字符。所以，使用两个指针来限定窗口大小，当超过k个不同的字符的时候，就调整窗口大小，而调整窗口的时候，需要用字符出现的频率来区分去除的字符是重复的还是不重复的。

代码：

java：

public class Solution {
    /**
     * @param s: A string
     * @param k: An integer
     * @return: An integer
     */
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        // write your code here
        if(s == null ||s.length() == 0 || k == 0) return 0;
        
        int[] count = new int[256];
        int res = 0, start = 0, distLen = 0;
        char[] array = s.toCharArray();
        for (int i = 0; i < array.length; i++) {
            if (count[array[i]]  == 0) distLen++;
            count[array[i]]++;
          
            // make window is valid
            if (distLen > k) {
                count[array[start]]--;
                if (count[array[start]] == 0) distLen--;
                start++;
            }
     
            res = i - start + 1;
        }

        return res;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019年07月15日，如有侵权请联系 cloudcommunity@tencent.com 删除

javascript