Java divide and conquer


  • 0
    S

    The result must fall into the substring regions which are partitioned by characters with < k occurrence. For example:

    "bbaeaaeecbd", k = 3.
    c and d have occurrence < 3. The original string is therefore partitioned into "bbaeaaee" and "b"
    bbaeaaee [c] b [d]

    Then, in the next level of recursion, bbaeaaee is partitioned to [b] [b] aeaaee

    Do this over and over.

    public int longestSubstring(String s, int k) {
            if (s.length() < k) {
                return 0;
            }
    
            int[] map = new int[26];
            for (int i = 0; i < s.length(); i++) {
                map[s.charAt(i) - 'a']++;
            }
    
            Set<Character> set = new HashSet<>();
            for (int i = 0; i < 26; i++) {
                if (0 < map[i] && map[i] < k) {
                    set.add((char) ('a' + i));
                }
            }
    
            if (set.isEmpty()) {
                return s.length();
            } else {
                int ans = 0, start = 0;
                for (int i = 0; i < s.length(); i++) {
                    if (set.contains(s.charAt(i))) {
                        int a = longestSubstring(s.substring(start, i), k);
                        ans = Math.max(ans, a);
                        start = i + 1;
                    }
                }
                ans = Math.max(ans, longestSubstring(s.substring(start), k));
                return ans;
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.