395. Longest Substring with At Least K Repeating Characters
in leetcode with 0 comment

395. Longest Substring with At Least K Repeating Characters

in leetcode with 0 comment

395. Longest Substring with At Least K Repeating Characters

原题链接 395. Longest Substring with At Least K Repeating Characters

解析思路

我们来思考一下什么样的情况可能可以构成连续的子串,每个字符都出现了至少k次;什么情况下又构不成?
很显然如果字符串里有字符在整个串里都没出现k次,那么含有这个字符的子串一定是不可能成立的。所以我们可以通过这些小于k次的字符作为分隔符 把长字符串分成一个个子串, 采用分支算法求字符串中符合条件的长度 返回其中最长的。

AC代码

public int longestSubstring(String s, int k) {
        return longestSubstring(s, 0, s.length() - 1, k);
    }

    public int longestSubstring(String s, int begin, int end, int k) {
        if (end - begin + 1 < k) {
            return 0;
        }
        int[] chs = new int[26];
        // 计算出现次数
        for (int i = begin; i <= end; i++) {
            chs[s.charAt(i) - 'a'] = chs[s.charAt(i) - 'a'] + 1;
        }
        // 跳过 次数小于k的
        while (begin < end && chs[s.charAt(begin) - 'a'] < k) {
            begin++;
        }
        while (begin < end && chs[s.charAt(end) - 'a'] < k) {
            end--;
        }
        if (end - begin + 1 < k) {
            return 0;
        }
        // 分而治之
        for (int i = begin; i <= end; i++) {
            if (chs[s.charAt(i) - 'a'] < k) {
                return Math.max(longestSubstring(s, begin, i - 1, k), longestSubstring(s, i + 1, end, k));
            }
        }
        return end - begin + 1;
    }