package leetcode;

/**
 * https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
 */
public class Problem395 {
    public int longestSubstring(String s, int k) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem395 prob = new Problem395();
        System.out.println(prob.longestSubstring("aaabb", 3)); // 3
        System.out.println(prob.longestSubstring("ababbc", 2)); // 5
        System.out.println(prob.longestSubstring("aaabcb", 3)); // 3
        System.out.println(prob.longestSubstring("aaabcbc", 2)); // 7
        System.out.println(prob.longestSubstring("aadabcbc", 2)); // 4
        System.out.println(prob.longestSubstring("aadabcbcd", 2)); // 9
        System.out.println(prob.longestSubstring("aadabdbbdc", 2)); // 9
    }
}

@@ -12,16 +12,65 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -247,32 +247,1230 @@
     
-// TODO%0A        return 0
+return longestSubstring(s, k, 0, s.length(), new HashMap%3C%3E());%0A    %7D%0A%0A    private static int longestSubstring(String s, int k, int left, int right,%0A                                        Map%3CString, Integer%3E memo) %7B%0A        if (left %3E= right) %7B%0A            return 0;%0A        %7D%0A        String key = left + %22%7C%22 + right;%0A        if (memo.containsKey(key)) %7B%0A            return memo.get(key);%0A        %7D%0A        String sub = s.substring(left, right);%0A        Map%3CCharacter, Integer%3E map = new HashMap%3C%3E();%0A        for (char c : sub.toCharArray()) %7B%0A            if (!map.containsKey(c)) %7B%0A                map.put(c, 1);%0A            %7D else %7B%0A                map.put(c, map.get(c) + 1);%0A            %7D%0A        %7D%0A        boolean valid = true;%0A        for (int val : map.values()) %7B%0A            if (val %3C k) %7B%0A                valid = false;%0A                break;%0A            %7D%0A        %7D%0A        int a = (!valid) ? 0 : sub.length();%0A        int b = longestSubstring(s, k, left + 1, right, memo);%0A        int c = longestSubstring(s, k, left, right - 1, memo);%0A        int d = longestSubstring(s, k, left + 1, right - 1, memo);%0A        int max = Math.max(a, Math.max(b, Math.max(c, d)));%0A        memo.put(key, max);%0A        return max
 ;%0A  

Update problem 395