public int longestSubstring(String s, int k) {
char[] str = s.toCharArray();
return helper(str,0,s.length(),k);
}
private int helper(char[] str, int start, int end, int k){
if(endstart<k) return 0;//substring length shorter than k.
int[] count = new int[26];
for(int i = start;i<end;i++){
int idx = str[i]'a';
count[idx]++;
}
for(int i = 0;i<26;i++){
if(count[i]<k&&count[i]>0){ //count[i]=0 => i+'a' does not exist in the string, skip it.
for(int j = start;j<end;j++){
if(str[j]==i+'a'){
int left = helper(str,start,j,k);
int right = helper(str,j+1,end,k);
return Math.max(left,right);
}
}
}
}
return endstart;
}
Java divide and conquer(recursion) solution


I rewrite it in C++ and simplify some parts of code.
class Solution { public: int longestSubstring(string s, int k) { return helper(0,s.size()1, s, k); } int helper(int begin, int end, string & s, int k) { if(end<begin) return 0; if(endbegin+1<k) return 0; vector<int> num_of(26,0); for(int i=begin; i<=end; i++) { int idx = s[i]  'a'; num_of[idx] ++; } int len = end  begin + 1; for(int j=begin; j<=end; j++) { if(num_of[s[j]  'a'] < k) { int left = helper(begin,j1,s,k); int right = helper(j+1, end,s,k); len = max(left, right); return len; } } return len; } };

@Nakanu same to you, but with less lines code
public int longestSubstring(String s, int k) { char[] a = s.toCharArray(); return helper(a, 0, s.length(), k); } public int helper(char[] a, int st, int en, int k) { if(en<=st  k>enst) return 0; int[] cnt = new int[26]; for(int i=st; i<en; i++) cnt[a[i]'a']++; for(int i=0; i<26; i++) { if(cnt[i]==0) continue; if(cnt[i] < k) { for(int j=st; j<en; j++) { if(a[j]==i+'a') { return Math.max(helper(a, st, j, k), helper(a, j+1, en, k) ); } } } } return enst; }

@xiaoyaoworm
Well. It has been a long time since I wrote this solution.
First, let us see how does this code work.
The idea is to keep finding the character which does not satisfy the requirement. (repeat less than k times).
And divide the problem into 2 parts, to find the longest substring on the lhs and rhs of the breaking point.For divide and conquer, it needs O(log(n)) calls of helper function to check the entire string and in the helper function, it costs O(n) to find such breaking point. In total, this algorithm is O(nlog(n)).Edit: The analysis was not correct. It should be O(n^2).

Shorter and faster :)
@quantumlaser, @DecaYaleint longestSubstring(const string &s, int k) { return helper(s, 0, s.size(), k); } int helper(const string &s, int beg, int end, int k){ if(end  beg < k) return 0; int cnt[26]{}; for(int i = beg; i < end; ++i) ++cnt[s[i]'a']; for(int i = beg; i < end; ++i) if (cnt[s[i]  'a'] < k) return max(helper(s, beg, i, k), helper(s, i + 1, end, k)); return end  beg; }



why do you need the outer loop?
for (int i = 0; i < 26; i++) { ... }
this one?
This is my 4 ms accepted code without it:
public int longestSubstring(String s, int k) { return dc(s, 0, s.length(), k); } public int dc(String s, int start, int end, int k) { if (end  start < k) return 0; int[] cnt = new int[26]; for (int i = start; i < end; i++) { cnt[s.charAt(i)  'a']++; } for (int i = start; i < end; i++) { if (cnt[s.charAt(i)  'a'] < k) { return Math.max(dc(s, start, i, k), dc(s, i + 1, end, k)); } } return end  start; }

@marcusgao94 it's not needed, but it makes it less likely that you will split close to the beginning of your 'start' index (which is bad. you want to split in the middle). further proof is that OP's code takes 3ms


@notturno Thank you for your suggestion! Yea, some codes are redundant. I have modified my code.
For the toCharArray(), I did that cuz it is faster to do it rather than keep calling String.charAt().

In my attempts to understand this clever solution, I refactored it and added some comments:
This solution uses Strings rather than character arrays, but that's just a personal preference (performance is still 3ms).
public class Solution { /** * Given a String s and an integer k, return the longest "valid" substring, * where a substring is valid iff every character in the substring occurs * at least k times. * * @param s The given String * @param k The minimum number of times all substring characters must occur * @return The length of the longest valid substring */ public int longestSubstring(String s, int k) { // Call divide and conquer helper method return div(s, 0, s.length(), k); } /** * Determines the length of the longest valid substring. * * We achieve this by recursively splitting the given String on characters * who do not occur at least k times (since they cannot be part of the * longest valid substring). * * Note that the substring of the current recursion is always equivalent * to s.substring(start, end). For space reasons, we don't ever actually * create a new substring. * * @param s The given String * @param start The beginning of the substring, inclusive * @param end The end of the substring, exclusive * @param k The minimum number of times all substring characters must occur * @return The length of the longest valid substring */ private int div(String s, int start, int end, int k) { /** * Base Case 1 of 2: * * If this substring is shorter than k, then no characters in it * can be repeated k times, therefore this substring and all * substrings that could be formed from it are invalid, * therefore return 0. */ if (end  start < k) return 0; /** * Count the frequency of characters in this substring. * * We are guaranteed from the problem statement that the given String * can only contain lowercase (English?) characters, so we use a * table of length 26 to store the character counts. */ int[] a = new int[26]; for (int i = start; i < end; i++) { a[s.charAt(i)'a']++; } // For every character in the above frequency table for (int i = 0; i < a.length; i++){ /** * If this character occurs at least once, but fewer than k times * in this substring, we know: * (1) this character cannot be part of the longest valid substring, * (2) the current substring is not valid. * * Hence, we will "split" this substring on this character, * wherever it occurs, and check the substrings formed by that split */ if (a[i] > 0 && a[i] < k) { /** * Look for each occurrence of this character (i + 'a') * in this substring. */ for (int j = start; j < end; j++) { if (s.charAt(j) == i + 'a') { // "Split" into two substrings to solve recursively int l = div(s, start, j, k); int r = div(s, j + 1, end, k); return Math.max(l, r); } } } } /** * Base Case 2 of 2: * * If every character in this substring occurs at least k times, * then this is a valid substring, so return this substring's length. */ return end  start; } }

@hide I think it's O(n^3) for your example? n iteration, n dividing ways, n letter to scan for each dividing.

@shadowless The n iteration + n letter to scan should be 2n, which equal to n not n^2. Plus the n dividing ways, I think total running time still should be O(n^2).