Given a string s and an integer k, find the oldest string in s and require that each character in the string occur at least k times. Returns the length of this substring

Leetcode-cn.com/problems/lo…

Example 1:

Input: s = “aaabb”, k = 3 Output: 3 Explanation: The oldest string is “aaa”, where the ‘a’ is repeated three times.

Example 2:

Input: s = “ababbc”, k = 2 Output: 5 Explanation: The oldest string is “ababb”, where ‘a’ is repeated twice and ‘b’ is repeated three times.

Tip:

1 <= S. length <= 104 s Consists of lowercase letters only. 1 <= k <= 105

Java solution

Ideas:

  • The substring must contain all letters greater than k
  • Idea 1:
    • Filter out the children and parents that do not meet the number
    • Slide the window to traverse
      • If the number of letters does not meet the requirements of the self-check, remove the number of letters that do not meet the requirements of the length
    • Record the maximum value until traversal is complete
  • Refer to divide and rule thought: actually already thought of, but did not divide and rule completely go down
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 {
            returnlen; }}}Copy the code

The official solution

Leetcode-cn.com/problems/lo…

  1. Divide and conquer: Think alike
  2. Sliding Windows: As I expected, checking the interior brought a lot of complexity to the record