java divide and conquer solution, easy to understand


  • 1
    public class Solution {
        public int longestSubstring(String s, int k) {
            if(s == null || s.length() == 0) {
                return 0;
            }
            HashMap<String,Integer> memo = new HashMap<String,Integer>(); 
            return helper(s , k , memo);
        }
        
        protected int helper(String s , int k , HashMap<String,Integer> memo) {
            if(s == null || s.length() == 0) return 0;
            if(memo.containsKey(s)) return memo.get(s);
            int res = 0;
            HashMap<Character,List<Integer>> map = new HashMap<Character,List<Integer>>();
            for(int i = 0 ; i < s.length() ; i++) {
                char c = s.charAt(i);
                if(map.containsKey(c)) {
                    map.get(c).add(i);
                }else {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(i);
                    map.put(c , list);
                }
            }
            boolean tag = false;
            for(List<Integer> list : map.values()) {
                if(list.size() < k) {
                    tag = true;
                    int index1 = list.get(0);
                    int index2 = list.get(list.size() - 1);
                    String left = s.substring(0 , index1);
                    String right = s.substring(index2+1);
                    if(list.size() == 1 || list.size() > 2) {
                        res = Math.max(helper(left , k , memo) , helper(right , k , memo));
                    }else {
                        String mid = s.substring(index1+1 , index2);
                        res = Math.max(helper(mid , k , memo) , Math.max(helper(left , k , memo) , helper(right , k , memo)));
                    }
                }
            }
            if(tag) {
                memo.put(s , res);
                return res;
            }else {
                memo.put(s , s.length());
                return s.length();
            }
        }
    }

Log in to reply
 

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