Java Divide and Conquer + brief explanation


  • 0
    A

    The solution is to use divide and conquer approach. Lets first count how many times appears each character in the string s. Then we can use the fact that the i-th character's counter which is less than k will not exist in the answer. So, we need to divide into two parts and search the best answer from those two parts: [start, i-1] and [i+1, end].

    public class Solution {
        public int longestSubstring(String s, int k) {
            if (s.length()<k) return 0;
            HashMap<Character, Integer> counts = getCounts(s);
            for (int i=0; i<s.length(); i++) {
                if (counts.get(s.charAt(i))<k) {
                    int left = longestSubstring(s.substring(0, i), k);
                    int right = longestSubstring(s.substring(i+1), k);
                    return  Math.max(left, right);
                }
            }
            return s.length();
        }
        
        private HashMap<Character, Integer> getCounts(String s) {
            HashMap<Character, Integer> counts = new HashMap<>();
            for (int i=0; i<s.length(); i++) {
                counts.put(s.charAt(i), counts.getOrDefault(s.charAt(i), 0) +1);
            }
            return counts;
        }
    }
    

Log in to reply
 

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