LeetCode刷题集Android开发经验谈Android开发

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

2021-04-28  本文已影响0人  Shimmer_

给你一个字符串 s 和一个整数 k ,请你找出 s 中的最长子串, 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度

https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/

示例1:

输入:s = "aaabb", k = 3
输出:3
解释:最长子串为 "aaa" ,其中 'a' 重复了 3 次。

示例2:

输入:s = "ababbc", k = 2
输出:5
解释:最长子串为 "ababb" ,其中 'a' 重复了 2 次, 'b' 重复了 3 次。

提示:

1 <= s.length <= 104
s 仅由小写英文字母组成
1 <= k <= 105

Java解法

思路:

  • 子串当中包含所有 字母个数必须大于k
  • 设想1:
    • 过滤出不满足个数的子母
    • 滑动窗口进行遍历
      • 遇到不满足个数字母时自检,移除个数不满足长度的部分
    • 记录最大值,直到遍历完成
  • 参考分治思想:实际已经想到了,但是没有完全分治下去
package sj.shimmer.algorithm.m4_2021;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by SJ on 2021/4/28.
 */

class D91 {
    public static void main(String[] args) {
//        System.out.println(longestSubstring("aaabb", 3));
//        System.out.println(longestSubstring("ababb", 3));
        System.out.println(longestSubstring("ababb", 2));
    }

    public static int longestSubstring(String s, int k) {
        if (s == null || s.length() < k) {
            return 0;
        }
        int len = s.length();
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            Integer num = map.getOrDefault(s.charAt(i), 0);
            map.put(s.charAt(i), ++num);
        }
        Character split = null;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (entry.getValue()<k) {
                split = entry.getKey();
                break;
            }
        }
        if (split!=null) {
            String[] splits = s.split(String.valueOf(split));
            int num = 0;
            for (String s1 : splits) {
                num = Math.max(num, longestSubstring(s1, k));
            }
            return num;
        } else {
            return len;
        }
    }
}
image

官方解

https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/solution/zhi-shao-you-kge-zhong-fu-zi-fu-de-zui-c-o6ww/

  1. 分治:思路一致
  2. 滑动窗口:和我设想差不多,校验内部时带来了很多的复杂记录
上一篇下一篇

猜你喜欢

热点阅读