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

• 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);
}
}
List<Integer> less=new ArrayList<Integer>();
for(char c:map.keySet()){
if(map.get(c).size()<k){
}
}
if(less.size()==0){
return end-start+1;
}
int max=0;
Collections.sort(less);
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;
}
``````

}

• 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.

• 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?

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

• 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

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