首页 > 其他 > 详细

leetcode395-至少有 K 个重复字符的最长子串

时间:2021-07-05 15:35:35      阅读:22      评论:0      收藏:0      [点我收藏+]
class Solution {
    public int longestSubstring(String s, int k) {
        int len = s.length();
        return dfs(s, 0, len-1, k);
    }

    public int dfs(String s, int l, int r, int k) {
        //先统计字符串s中,每个字母出现的次数,一共有26个小写字母
        int[] num = new int[26];
        for (int i = l; i <= r; i++) {
            num[s.charAt(i) - ‘a‘]++;
        }

        // 然后找到字符串s中第一个不满足题意的字符
        char splite = 0;
        for (int i = 0; i < 26; i++) {
            if (num[i] > 0 && num[i] < k) {
                splite = (char) (i+‘a‘);
                break;
            }
        }

        // 如果没找到不满足题意的字符,说明字符串s符合题意,直接返回字符串s的本身(最长)长度
        if (splite == 0) {
            return r-l+1;
        }

        // 如果找到了字符splite,就要以splite为界划分子串
        int i = l;
        int res = 0;
        while (i<=r) {
            // 先找到第一个不等于splite的字符下标
            while (i<=r && s.charAt(i) == splite) {
                i++;
            }

            if (i > r) {
                break;
            }
            int start = i;  // 保存一下结果
            // 再找最后一个不等于splite的下标
            while(i<=r && s.charAt(i) != splite) {
                i++;
            }
            
            // 分治
            int len = dfs(s, start, i-1, k);
            res = Math.max(res, len);
        }

        return res;
    }
}

 

leetcode395-至少有 K 个重复字符的最长子串

原文:https://www.cnblogs.com/xiazhenbin/p/14971333.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!