LeetCode 395. Longest Substring with At Least K Repeating Characters（Sliding Window）

Longest Substring with At Least K Repeating Characters

Medium

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:

s = “aaabb”, k = 3

Output:

3

The longest substring is “aaa”, as ‘a’ is repeated 3 times.

Example 2:

Input:

s = “ababbc”, k = 2

Output:

5

The longest substring is “ababb”, as ‘a’ is repeated 2 times and ‘b’ is repeated 3 times.

题意

给定一个字符串s和一个正整数k，找到s的最大子串，使得s中所有的字母最少出现k次，求该子串的最大长度

思路

Sliding Window. 字母最多有26种可能，w遍历1~26，考虑子串中含有w个不同的字母的个数，分别通过Sliding Window求w个不同字母在子串中出现次数>=k的子串的最大长度

代码

class Solution {
    public int longestSubstring(String s, int k) {
        int n = s.length(), i = 0, j = 0, ans = 0, uniques = 0, w = 0, numK = 0, idx = 0;    
        // w: number of distinct character considered
        // numK: number of characters appearing more than k times in the window
        // uniques: number of distinct characters in the window
        int[] cnt = new int[26];
        for (w = 1; w <= 26; ++w) {
            i = 0;
            j = 0;
            uniques = 0;
            numK = 0;
            Arrays.fill(cnt, 0);
            while (j < n && i <= j) {
                if (uniques <= w) {
                    idx = s.charAt(j++) - 'a';
                    if (cnt[idx] == 0) {
                        ++uniques;
                    }
                    ++cnt[idx];
                    if (cnt[idx] == k) {
                        ++numK;
                    }
                } else {
                    idx = s.charAt(i++) - 'a';
                    if (cnt[idx] == k) {
                        --numK;
                    }
                    --cnt[idx];
                    if (cnt[idx] == 0) {
                        --uniques;
                    }
                }
                if (uniques == w && uniques == numK) {
                    ans = Math.max(j - i, ans);
                }
            }
        }
        return ans;
    }
}