Java (nlogn) recursive solution by dividing the string into substrings(15ms)


  • 4
    X

    Count the times that each characters appear, and if any characters appear less than k time, divide the string to substring until the substring meets the requirement

    public class Solution {

    public int longestSubstring(String s, int k) {
        char[] schar=s.toCharArray();
        return longest(schar,0,schar.length-1,k);
    }
    public int longest(char[] schar,int start,int end,int k){
        if(end-start+1<k){
            return 0;
        }
        Map<Character,List<Integer>> map=new HashMap<Character,List<Integer>>();
        for(int i=start;i<=end;i++){   //count hwo many times each characters appears
            if(!map.containsKey(schar[i])){
                List<Integer> newlist=new ArrayList<Integer>();
                map.put(schar[i],newlist);
            }
            map.get(schar[i]).add(i);
        }
        List<Integer> less=new ArrayList<Integer>();
        for(char c:map.keySet()){
            if(map.get(c).size()<k){
                less.addAll(map.get(c));
            }
        }
        if(less.size()==0){
            return end-start+1;
        }
        int max=0;
        Collections.sort(less);
        less.add(end+1);
        int last=start-1;
        for(int i=0;i<less.size();i++){               //divide the string into substrirng
            int cur=less.get(i);
            max=Math.max(max,longest(schar,last+1,cur-1,k));
            last=cur;
        }
        return max;
    }
    

    }


  • 0

    You should update int last = -1; to int last = start; since you don't need to go over the beginning substring again. This will increase the efficiency a lot.


  • 0
    X

    @ILoveGoogle Thanks for your reply, I have already update my code


  • 0
    Y

    Nice solution. But I doubt the worse case is O(nlogn). The are logn levels, but in each level you do sorting, so each level cannot be O(n) I guess?


  • 0
    L

    On worst case, it could be n^2 as it doesn't guarantee equally divide.


  • 0

    Nice solution, this solution is the optimization of the top voted one: https://discuss.leetcode.com/topic/57372/java-divide-and-conquer-recursion-solution/16

    Each recursion divide the string into mutual exclusive chunks, which avoid duplicate computations of toped voted solution


Log in to reply
 

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