Wednesday, September 7, 2016

LeetCode 395 - Longest Substring with At Least K Repeating Characters


https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
Example 1:
Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:
Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
X.
https://discuss.leetcode.com/topic/57501/java-20-lines-very-easy-solution-7ms-with-explanation/2
https://tech.liuchao.me/2016/09/leetcode-solution-395/
    public int longestSubstring(String s, int k) {
        if (s.length() < k) return 0;
        int[] count = new int[26];
        for (char c: s.toCharArray()) {
            count++;
        }
        List<String> badChars = new ArrayList<>();
        for (int i = 0; i < count.length; i++) {
            if (count[i] < k && count[i] != 0) badChars.add(String.valueOf((char)(i + 'a')));
        }
        if (badChars.isEmpty()) return s.length();
        int result = 0;
        String[] targets = s.split(String.join("|", badChars));
        for (String tmpString: targets) {
            result = Math.max(result, longestSubstring(tmpString, k));
        }
        return result;
    }
http://www.voidcn.com/blog/niuooniuoo/article/p-6199475.html


 public int longestSubstring(String s, int k) {
  if (s == null || s.length() == 0) return 0;
  int[] nums = new int[26];
  char[] chars = s.toCharArray();
  for (char c : chars) nums[c - 'a']++;
  boolean valid = false, flag = false;
  for (int num : nums) {
   if (num >= k) valid = true;
   if (num > 0 && num < k) flag = true;
   if (valid && flag) break;
  }
  if (!valid) return 0;// invalid: no char in s appears >= k times.
  if (!flag) return s.length();//!flag: every char appears >= k times.
  int max = 0, start = 0, cur = 0;
  for (int i = 0; i < s.length(); i++) {
   if (nums[chars[i] - 'a'] < k) {
    max = Math.max(max, longestSubstring(s.substring(start, i), k));
    start = i + 1;
   }
  }
  max = Math.max(max, longestSubstring(s.substring(start), k));
  return max;
 }

https://discuss.leetcode.com/topic/57265/java-d-c-solution
https://discuss.leetcode.com/topic/57372/java-3ms-divide-and-conquer-recursion-solution
The idea is pretty basic, find the point where we should split the string, eg, the position of character which total count is <k, then dfs it then find the max.
For Example: bbcddefegaghfh and 2, so we shall dfs on "bb", "ddefeg", "ghfh", since a , c only appears1 for once.
public int longestSubstring(String s, int k) {
       if (s == null || s.length() < k || k == 0 ) return 0;
       int max = 0;
       int[] count = new int[26];
       int res = 0;
       for (int i = 0; i < s.length(); i++) {
           count[s.charAt(i) - 'a']++;
       }
       List<Integer> pos = new ArrayList<Integer>();
       for (int i = 0; i < s.length(); i++) {
           if (count[s.charAt(i) - 'a'] < k) pos.add(i);
       }
       if (pos.size() == 0) return s.length();
       pos.add(0, -1);
       pos.add(s.length());
       for (int i = 1; i < pos.size(); i++) {
           int start = pos.get(i-1) + 1;
           int end = pos.get(i);
           int next = longestSubstring(s.substring(start, end), k);
           res = Math.max(res, next);
       }
       return res;
   }
https://discuss.leetcode.com/topic/57092/4-lines-python/
Only 7ms for Java solution without looking for the least occurred character, i.e., split the string by any character that doesn't appear for k times.
    public int longestSubstring(String s, int k) {
        int n = s.length();
        if (n==0 || n<k) return 0;
        if (k==1) return n;
        int[] counts = new int[26];
        for (char c: s.toCharArray()) counts[c-'a']++;
        boolean valid = true;
        char badchar = 0;
        for (int i=0; i<26; i++) {
            if (counts[i]>0 && counts[i]<k) {
                badchar = (char)(i+'a');
                break;
            }
        }
        if (badchar==0) return n;
        String[] subs = s.split(badchar+"");
        int res = 0;
        for (String sub:subs) res = Math.max(res, longestSubstring(sub,k));
        return res;
    }

public int longestSubstring(String s, int k) {
    if (s.length() == 0 || k == 1) return s.length();
    if (s.length() < k) return 0;
    
    int[] count = new int[26];
    for (char c : s.toCharArray()) count[c-'a'] ++;
    boolean eligible = true;
    for (int i = 0; i < 26; i ++) {
        if (count[i] != 0 && count[i] < k) {eligible = false;break;}
    }
    if (eligible) return s.length();
    char least = 0;
    for (int i = 0; i < 26; i ++) {
        if (count[i] != 0 && least == 0) {least = (char)(i+'a');continue;} 
        if (count[i]!=0 && count[i] < count[least - 'a']) least = (char)(i+'a');
    }
    String[] sub = s.split(least+"");
    int res = 0;
    for (String str : sub) {
        res = Math.max(res, longestSubstring(str, k));
    }
    return res;
}

As pointed out by @hayleyhu, I can just take the first too rare character instead of a rarest. Submitted once, accepted in 48 ms.
def longestSubstring(self, s, k):
    for c in set(s):
        if s.count(c) < k:
            return max(self.longestSubstring(t, k) for t in s.split(c))
    return len(s)

Original:

def longestSubstring(self, s, k):
    if len(s) < k:
        return 0
    c = min(set(s), key=s.count)
    if s.count(c) >= k:
        return len(s)
    return max(self.longestSubstring(t, k) for t in s.split(c))
If every character appears at least k times, the whole string is ok. Otherwise split by a least frequent character (because it will always be too infrequent and thus can't be part of any ok substring) and make the most out of the splits.
https://discuss.leetcode.com/topic/57134/two-short-c-solutions-3ms-and-6ms
Sol1: a simple improvement on the naive quaratic solution. The idea is that if a locally longest substr is found, there's no need to check substrs overlapping it.
Sol1 can run O(n) times in some cases, but worst case is O(n2).
int longestSubstring(string s, int k) {
   int max_len = 0;
   for (int first = 0; first+k < s.size();) {
       int count[26] = {0};
       int mask = 0;
       int max_last = first;
       for (int last = first; last < s.size(); ++last) {
           int i = s[last] - 'a';
           count[i]++;
           if (count[i]<k) mask |= (1 << i);
           else   mask &= (~(1 << i));
           
           if (mask == 0) {
               max_len = max(max_len, last-first+1);
               max_last = last;
           }
       }
       first = max_last + 1;
   }
   return max_len;
}
Sol2: recursive: split the string into substrs by characters of occurrence less than k. Then recursively apply the problem to each substr.
Worst case of Sol2 is O(n), because there are at most 26 levels of recursions. The C++ impl. runs 6ms. I suspect this is because the current test cases does not cover enough cases in favor of this solution in run time.
int longestSubstring(string s, int k) {
    return longestSubstring_recur(s, k, 0, s.size());
}

int longestSubstring_recur(const string& s, int k, int first, int last) {
    int count[26] = {0};
    for (int j = first; j < last; ++j) ++count[s[j] - 'a'];
    
    int max_len = 0;
    for (int j = first; j < last;) {
        while (j < last && count[s[j]-'a']<k) ++j;
        if (j == last) break;
        int l = j;
        while (l < last && count[s[l]-'a']>=k) ++l;
        //all chars appear more than k times
        if (j == first && l == last) return last-first; 
        max_len = max(max_len, longestSubstring_recur(s, k, j, l));
        j = l;
    }
    return max_len;
}
http://www.cnblogs.com/grandyang/p/5852352.html
发现我当时的没做出来的原因主要是卡在了如何快速的判断某一个字符串是否所有的元素都已经满足了至少出现k次这个条件,虽然我也用哈希表建立了字符和其出现次数之间的映射,但是如果每一次都要遍历哈希表中的所有字符看其出现次数是否大于k,未免有些不高效。而用mask就很好的解决了这个问题,由于字母只有26个,而整型mask有32位,足够用了,每一位代表一个字母,如果为1,表示该字母不够k次,如果为0就表示已经出现了k次,这种思路真是太聪明了,隐约记得这种用法在之前的题目中也用过,但是博主并不能举一反三(沮丧脸:(),还得继续努力啊。我们遍历字符串,对于每一个字符,我们都将其视为起点,然后遍历到末尾,我们增加哈希表中字母的出现次数,如果其小于k,我们将mask的对应位改为1,如果大于等于k,将mask对应位改为0。然后看mask是否为0,是的话就更新res结果,然后把当前满足要求的子字符串的起始位置j保存到max_idx中,等内层循环结束后,将外层循环变量i赋值为max_idx+1,继续循环直至结束
    int longestSubstring(string s, int k) {
        int res = 0, i = 0, n = s.size();
        while (i + k < n) {
            int m[26] = {0}, mask = 0, max_idx = i;
            for (int j = i; j < n; ++j) {
                int t = s[j] - 'a';
                ++m[t];
                if (m[t] < k) mask |= (1 << t);
                else mask &= (~(1 << t));
                if (mask == 0) {
                    res = max(res, j - i + 1);
                    max_idx = j;
                }
            }
            i = max_idx + 1;
        }
        return res;
    }


X.
http://www.guoting.org/leetcode/leetcode-395-longest-substring-with-at-least-k-repeating-characters/
首先,跟通常的类似题目的处理方式一样,我们先统计出字符串中每个字符出现的次数,如果统计出来的每个字符出现的次数都不小于k,说明原字符串是符合条件的,直接返回原字符串的长度即可;如果统计出来的字符次数有小于k的,说明直接返回原字符串的长度已经不合适了,因为有的字符不符合条件,那么这时候我们应该怎么做呢?
我们想,既然我们已经知道了原字符串中有些字符出现的次数是小于k的,那么我们要求的满足题目条件的最长子串中肯定是不能包含这些字符的,那么我们应该怎么做呢?
我们这样做,我们记录下这些字符在原字符串中出现的位置,这些字符会把原字符串分成一段一段的,但是分割之后的字符子串也不一定肯定符合条件,仍需要对每段进行判断,接下来我们对分割之后的每一段继续判断,找出其中的最大值即可。
    public int longestSubstring(String s, int k) {
        if(s==null||s.length()==0||s.length()<k) return 0;
        if(k<=1) return s.length();
        int n=s.length();
        int[] count=new int[26];
        int max=0;
        for(int i=0;i<n;i++){
            count[s.charAt(i)-'a']++;
        }
        List<Integer> pos=new ArrayList<>();
        for(int i=0;i<n;i++){
            if(count[s.charAt(i)-'a']<k) pos.add(i);
        }
        if(pos.size()==0) return n;
        pos.add(0,-1);
        pos.add(n);
        for(int i=1;i<pos.size();i++){
            int start=pos.get(i-1)+1;
            int end=pos.get(i);
            max=Math.max(max,longestSubstring(s.substring(start,end),k));
        }
        return max;
    }
http://www.programcreek.com/2014/09/leetcode-longest-substring-with-at-least-k-repeating-characters-java/
public int longestSubstring(String s, int k) {
    HashMap<Character, Integer> counter = new HashMap<Character, Integer>();
 
    for(int i=0; i<s.length(); i++){
 
        char c = s.charAt(i);
        if(counter.containsKey(c)){
            counter.put(c, counter.get(c)+1);
        }else{
            counter.put(c, 1);
        }
 
    }
 
    HashSet<Character> splitSet = new HashSet<Character>();
    for(char c: counter.keySet()){
        if(counter.get(c)<k){
            splitSet.add(c);
        }
    }
 
    if(splitSet.isEmpty()){
        return s.length();
    }
 
    int max = 0;
    int i=0, j=0;
    while(j<s.length()){
        char c = s.charAt(j);
        if(splitSet.contains(c)){
            if(j!=i){
                max = Math.max(max, longestSubstring(s.substring(i, j), k));
            }
            i=j+1;
        }
        j++;
    }
 
    if(i!=j)
         max = Math.max(max, longestSubstring(s.substring(i, j), k));
 
    return max;
}
https://all4win78.wordpress.com/2016/09/08/leetcode-395-longest-substring-with-at-least-k-repeating-characters/comment-page-1/
算法基本原理是,先遍历整个string,并记录每个不同的character的出现次数。如果所有character出现次数都不小于k,那么说明整个string就是满足条件的longest substring,返回原string的长度即可;如果有character的出现次数小于k,假设这个character是c,因为满足条件的substring永远不会包含c,所以满足条件的substring一定是在以c为分割参考下的某个substring中。所以我们需要做的就是把c当做是split的参考,在得到的String[]中再次调用我们的method,找到最大的返回值即可。
当然,这样每次都需要统计character的次数,不是特别高效,优化的话可以保存一个全局的数组来保存统计的次数,每一行是每个不同的character,而每一列是每个character在原始string中到某个位置时出现了多少次,所以大小应该是(# of different characters) x (length of original string)。当然这里具体细节还是有点复杂,需要的空间可能也会比较大(最差情况n*n)。我这里就偷懒没有实现,有兴趣的朋友可以自己试试看
http://blog.csdn.net/mebiuw/article/details/52449892
public int longestSubstring(String s, int k) { //System.out.println(s); int n = s.length(); if(n < k) return 0; int counter[] = new int[26]; boolean valid[] = new boolean[26]; char ss[] = s.toCharArray(); //统计每个字符的长度 for(int i=0;i<n;i++) counter[ss[i] - 'a']++; //检查当前字符串是否是完全满足的 boolean fullValid = true; //判断每个字符的出现条件是否合适,即,要么不出现,要么出现了不少于k for(int i=0;i<26;i++){ if(counter[i]>0 && counter[i]<k){ valid[i] = false; fullValid = false; } else valid[i] = true; } if(fullValid) return s.length(); int max = 0; int lastStart=0; //把不符合要求的断开,然后依次检查 取最大 for(int i=0;i<n;i++){ if(valid[ss[i] - 'a'] == false){ // System.out.println(lastStart+" "+i); max = Math.max(max,longestSubstring(s.substring(lastStart,i),k)); lastStart = i + 1; } } max = Math.max(max,longestSubstring(s.substring(lastStart,n),k)); return max; }

http://xiadong.info/2016/09/leetcode-395-longest-substring-with-at-least-k-repeating-characters/
先遍历一遍字符串, 记录每个字符的出现次数, 在这一步中同时记录出现大于等于k次的字母个数, 如果根本就没有大于等于k次的字母, 那么可以直接返回0.
通过出现次数不足k次的字母来把字符串分割成多个子串, 因为在原字符串中出现次数不足k次的字母必然不会出现在结果串中.
递归的处理每个子串. 递归结束条件为字符串长度不足k.
http://www.cnblogs.com/dongling/p/5843874.html

X.
https://scottduan.gitbooks.io/leetcode-review/content/longest_substring_with_at_least_k_repeating_charac.html
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)).
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(end<start) return 0;
    if(end-start<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]==0)continue;//i+'a' does not exist in the string, skip it.
        if(count[i]<k){
            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 end-start;
}
http://bookshadow.com/weblog/2016/09/04/leetcode-longest-substring-with-at-least-k-repeating-characters/
递归(Recursion)/ 分治法(Divide and Conquer)
统计原始字符串s中各字符的出现次数,统计其中出现次数少于k次的字符,得到数组filters。
若filters为空数组,则直接返回s的长度。
以filters为分隔符,将s拆分为若干子串,分别递归计算各子串的结果,返回最大值。
def longestSubstring(self, s, k): """ :type s: str :type k: int :rtype: int """ cnt = collections.Counter(s) filters = [x for x in cnt if cnt[x] < k] if not filters: return len(s) tokens = re.split('|'.join(filters), s) return max(self.longestSubstring(t, k) for t in tokens)

http://www.itdadao.com/articles/c15a340739p0.html
先统计出字符串中每个字符出现的次数,对于出现次数少于k的字符,任何一个包含该字符的字符串都不是符合要求的子串,因此这样的字符就是分隔符,应该以这些出现次数少于k次的字符做分隔符打断原字符串,然后对各个打断得到的字符串进行递归统计,得到最长的符合要求的字符串。如果一个字符串中不包含分隔符(即每个字符出现的次数都达到了k次及以上次数),那么这个字符串就是符合要求的子串。
    public int longestSubstring(String s, int k) {
        if(k<=1){
            return s.length();
        }
        
        int[] repeat=new int[128];
        for(int i=0;i<s.length();i++){
            repeat[s.charAt(i)]++;
        }
        StringBuilder reg=new StringBuilder("");
        boolean firstSplit=true;
        for(int i='a';i<='z';i++){
            if(repeat[i]>0&&repeat[i]<k){
                if(firstSplit){
                    reg.append((char)i);
                    firstSplit=false;
                }
                else{
                    reg.append("|"+(char)i);
                }
            }
        }
        if(reg.length()>0){
            //说明有分隔符
            String[] strs=s.split(reg.toString());
            int max=0;
            int tmpAns=0;
            for(String str:strs){ // if str.length< max, ignore it
                tmpAns=longestSubstring(str, k);
                if(tmpAns>max){
                    max=tmpAns;
                }
            }
            return max;
        }
        else{
            //没有分隔符,说明s中的每一个字符出现的次数都大于k
            return s.length();
        }
    }
https://discuss.leetcode.com/topic/57699/simple-java-o-n-solution
The exact time complexity is O(26n) = O(n), where n is the length of the input string.
The proof is simply that every time, we remove a letter (all of that one) from string (or sub-string). So the maximum level of recursion tree is 26, since there are only 26 letters in this case. And at each level, the total characters we need process are no more than n. Thus, the time complexity is O(n).
Visualization:
[00000000000000000000000000] number of kinds of letters remained: no more than L (L<=26);
[000000000].....[000000]...[00000] number of kinds of letters remained no more than L-1;

https://discuss.leetcode.com/topic/57092/6-lines-python
def longestSubstring(self, s, k):
    if len(s) < k:
        return 0
    c = min(set(s), key=s.count)
    if s.count(c) >= k:
        return len(s)
    return max(self.longestSubstring(t, k) for t in s.split(c))
If every character appears at least k times, the whole string is ok. Otherwise split by a least frequent character (because it will always be too infrequent and thus can't be part of any ok substring) and make the most out of the splits.

public int longestSubstring(String s, int k) {

    return divide(s,0,s.length()-1,k);        
}

private int divide(String s, int start, int end, int k){
    // pass impossible cases
    if(end<start) return 0;
    if(end-start+1<k) return 0;
    
    char[] schar = s.toCharArray();
    // count the occurence of each letter in the string from start and end;
    int[] cnt = new int[26];

    int max = 0;
    // count frequence of each character
    for(int i=start;i<=end;i++){
        int index = schar[i]-'a';
        cnt[index]++;
    }
    
    // check if there is a letter which occurence is smaller than k
    // if there it is, divide it and rerun.
    for(int i=0;i<26;i++){
        if(cnt[i]==0) continue;
        if(cnt[i]<k){
            char c = (char) (i+'a');
            int smaller = s.indexOf(c,start);
            if(smaller>=0){
                int left = divide(s,start,smaller-1,k);
                int right = divide(s,smaller+1,end, k);
                return Math.max(left, right);
            }else{
                return 0;
            }
        }
    }
    return end-start+1;  // if every letter comes along more than k times
}
https://discuss.leetcode.com/topic/57265/java-d-c-solution
The idea is pretty basic, find the point where we should split the string, eg, the position of character which total count is <k, then dfs it then find the max.
For Example: bbcddefegaghfh and 2, so we shall dfs on "bb", "ddefeg", "ghfh", since a , c only appears1 for once.
// use substring, not efficient, use char[] instead
public int longestSubstring(String s, int k) {
       if (s == null || s.length() == 0 || k == 0) return 0;
       int max = 0;
       int[] count = new int[26];
       int res = 0;
       for (int i = 0; i < s.length(); i++) {
           count[s.charAt(i) - 'a']++;
       }
       List<Integer> pos = new ArrayList<Integer>();
       for (int i = 0; i < s.length(); i++) {
           if (count[s.charAt(i) - 'a'] < k) pos.add(i);
       }
       if (pos.size() == 0) return s.length();
       pos.add(0, -1);
       pos.add(s.length());
       for (int i = 1; i < pos.size(); i++) {
           int start = pos.get(i-1) + 1;
           int end = pos.get(i);
           int next = longestSubstring(s.substring(start, end), k);
           res = Math.max(res, next);
       }
       return res;
   }
X. Iterative Version
https://discuss.leetcode.com/topic/57165/java-o-n-2-iterator-and-backtracking-solution
The first one is a simple solution of O(n^2), we find the max length starting at each character in s. The three if statement in for loop is to check if the string is satisfied, I use math methods instead of iterator the map each time to save time.
0_1473033447412_Screen Shot 2016-09-04 at 4.21.35 PM.png

http://edlinlink.github.io/Leetcode_Longest_Substring_With_At_Least_K_Repeating_Characters.html

2. MLE Code

    int longestSubstring(string s, int k )
    {
        int ans = 0;
        vector<int> count(26,0);                    
        for( int i=0; i<s.size(); i++ )
            count[s[i]-'a']++;

        for( int i=0; i<s.size(); i++ )
            if( count[s[i]-'a']<k )
                return max( longestSubstring(s.substr(0,i),k), longestSubstring(s.substr(i+1),k) );
        return s.size();
    }
Using recursion will lead to Memory Limit Exceeded. We do not need to calculate longestSubstring if the length of the string is less than current answer;

3. TLE Code

    int longestSubstring(string s, int k )
    {
        int ans = 0;
        vector<int> count(26,0);                    
        for( int i=0; i<s.size(); i++ )
            count[s[i]-'a']++;

        for( int i=0; i<s.size(); i++ ){
            if( count[s[i]-'a']<k ){
                int left = 0, right = 0;
                left = longestSubstring(s.substr(0,i),k);
                if( s.substr(i+1).size() > left)
                    right = longestSubstring(s.substr(i+1),k);
                return max( left, right );
            }
        }
        return s.size();
    }
Opps, recursion solution still Time Limit Exceeded. We now just split the substring into two parts, but actually after one statistic we can split the string into several parts.

4. Code

class Solution {
public:
    int longestSubstring(string s, int k )
    {
        int ans = 0;
        vector<int> count(26,0);                    
        for( int i=0; i<s.size(); i++ )
            count[s[i]-'a']++;

        int len = -1;
        for( int i=0; i<s.size(); i++ ){
            int index = 0;
            if( count[s[i]-'a']<k ){
                len = max( len, longestSubstring( s.substr(index, i-index), k ) );
                index = i+1;
            }
        }
        return ( -1 == len ? s.size() : len );
    }
https://all4win78.wordpress.com/2016/09/08/leetcode-395-longest-substring-with-at-least-k-repeating-characters/
算法基本原理是,先遍历整个string,并记录每个不同的character的出现次数。如果所有character出现次数都不小于k,那么说明整个string就是满足条件的longest substring,返回原string的长度即可;如果有character的出现次数小于k,假设这个character是c,因为满足条件的substring永远不会包含c,所以满足条件的substring一定是在以c为分割参考下的某个substring中。所以我们需要做的就是把c当做是split的参考,在得到的String[]中再次调用我们的method,找到最大的返回值即可。
当然,这样每次都需要统计character的次数,不是特别高效,优化的话可以保存一个全局的数组来保存统计的次数,每一行是每个不同的character,而每一列是每个character在原始string中到某个位置时出现了多少次,所以大小应该是(# of different characters) x (length of original string)。当然这里具体细节还是有点复杂,需要的空间可能也会比较大(最差情况n*n)
X.
https://discuss.leetcode.com/topic/57158/java-hashmap-solution-worst-case-o-n-2-26
These commented blocks are for speeding up the code, in case of Time Limit Exceed.Basically,denote index as the position of each character in String s,I use a HashMap<index,int[]> to store the occurence of all characters in input s[0,index],index inclusively,which, ranges from 0 to s.length()-1;every substring then can be expressed as map.get(i)-map.get(j), 0<=j<i, we can just check whether if it's valid,update the maxLen and also the hashmap.
I was totally inspired by a guy and he gave an idea of solving subarray/substring problem, and it's stunning!
https://discuss.leetcode.com/topic/33537/java-o-n-explain-how-i-come-up-with-this-idea
    public int longestSubstring(String s, int k) {
        HashMap<Integer,int[]> map=new HashMap<>();
        int maxLen=0;
        map.put(-1,new int[26]);
        for(int i=0;i<s.length();i++){
            int[] curr=Arrays.copyOf(map.get(i-1),26);
            curr[s.charAt(i)-'a']++;
            // if(i+1<k){
            //     map.put(i,curr);
            //     continue;
            // }
            for(int j=-1;j<i;j++){
                // if(i-j<k){
                //     continue;
                // }
                int[] tmp=map.get(j);
                boolean flag=true;
                for(int m=0;m<26;m++){
                    if(curr[m]!=tmp[m]&&curr[m]-tmp[m]<k){
                        flag=false;
                        break;
                    }
                }
                
                if(flag){
      maxLen=Math.max(maxLen,i-j);
                    break;
                }
            }
            map.put(i,curr);
       }
       return maxLen;
    }
TODO
http://www.2cto.com/px/201609/545934.html

No comments:

Post a Comment

Labels

GeeksforGeeks (976) Algorithm (811) LeetCode (654) to-do (599) Review (362) Classic Algorithm (334) Classic Interview (298) Dynamic Programming (263) Google Interview (233) LeetCode - Review (233) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (119) Bit Algorithms (110) Cracking Coding Interview (110) Smart Algorithm (109) Math (91) HackerRank (85) Lintcode (83) Binary Search (73) Graph Algorithm (73) Greedy Algorithm (61) Interview Corner (61) Binary Tree (58) List (58) DFS (56) Algorithm Interview (53) Advanced Data Structure (52) Codility (52) ComProGuide (52) LeetCode - Extended (47) USACO (46) Geometry Algorithm (45) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Jobdu (39) Interval (38) Recursive Algorithm (38) Stack (38) String Algorithm (38) Binary Search Tree (37) Knapsack (37) Codeforces (36) Introduction to Algorithms (36) Matrix (36) Must Known (36) Beauty of Programming (35) Sort (35) Space Optimization (34) Array (33) Trie (33) prismoskills (33) Backtracking (32) Segment Tree (32) Union-Find (32) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Data Structure Design (29) Company-Zenefits (28) Microsoft 100 - July (28) to-do-must (28) Random (27) Sliding Window (27) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Hash (22) Queue (22) DFS + Review (21) TopCoder (21) Binary Indexed Trees (20) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Pre-Sort (20) Company-Facebook (19) UVA (19) Probabilities (18) Follow Up (17) Codercareer (16) Company-Uber (16) Game Theory (16) Heap (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Iterator (15) Merge Sort (15) O(N) (15) Bisection Method (14) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Codechef (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) KMP (12) Long Increasing Sequence(LIS) (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Ordered Stack (11) Princeton (11) Tree DP (11) 挑战程序设计竞赛 (11) Binary Search - Bisection (10) Company - Microsoft (10) Company-Airbnb (10) Euclidean GCD (10) Facebook Hacker Cup (10) HackerRank Easy (10) Reverse Thinking (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) X Sum (10) Coin Change (9) Divide and Conquer (9) Lintcode - Review (9) Mathblog (9) Max-Min Flow (9) Stack Overflow (9) Stock (9) Two Pointers (9) Book Notes (8) Bottom-Up (8) DP-Space Optimization (8) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) Suffix Tree (8) System Design (8) Tech-Queries (8) Time Complexity (8) Use XOR (8) 穷竭搜索 (8) Algorithm Problem List (7) DFS+BFS (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Linked List (7) Longest Common Subsequence(LCS) (7) Math-Divisible (7) Miscs (7) O(1) Space (7) Probability DP (7) Radix Sort (7) Simulation (7) Xpost (7) n00tc0d3r (7) 蓝桥杯 (7) Bucket Sort (6) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) How To (6) Interviewstreet (6) Kadane’s Algorithm (6) Knapsack - MultiplePack (6) Level Order Traversal (6) Manacher (6) Minimum Spanning Tree (6) One Pass (6) Programming Pearls (6) Quick Select (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Suffix Array (6) Threaded (6) reddit (6) AI (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Crazyforcode (5) DFS+Cache (5) DP-Multiple Relation (5) DP-Print Solution (5) Dutch Flag (5) Fast Slow Pointers (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Inversion (5) Java (5) Kadane - Extended (5) Matrix Chain Multiplication (5) Microsoft Interview (5) Morris Traversal (5) Pruning (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sweep Line (5) Traversal Once (5) TreeMap (5) jiuzhang (5) to-do-2 (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Anagram (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Company-Amazon (4) Consistent Hash (4) Convex Hull (4) Cycle (4) DP-Include vs Exclude (4) Dijkstra (4) Distributed (4) Eulerian Cycle (4) Flood fill (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) Left and Right Array (4) MinMax (4) Multiple Data Structures (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Pre-Sum (4) Probability (4) Programcreek (4) Quick Sort (4) Spell Checker (4) Stock Maximize (4) Subsets (4) Sudoku (4) Symbol Table (4) TreeSet (4) Triangle (4) Water Jug (4) Word Ladder (4) algnotes (4) fgdsb (4) 最大化最小值 (4) A Star (3) Abbreviation (3) Algorithm - Brain Teaser (3) Algorithm Design (3) Anagrams (3) B Tree (3) Big Data Algorithm (3) Binary Search - Smart (3) Caterpillar Method (3) Coins (3) Company - Groupon (3) Company - Indeed (3) Cumulative Sum (3) DP-Fill by Length (3) DP-Two Variables (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Edit Distance (3) Expression (3) Finite Automata (3) Forward && Backward Scan (3) Github (3) GoLang (3) Include vs Exclude (3) Joseph (3) Jump Game (3) Knapsack-多重背包 (3) LeetCode - Bit (3) LeetCode - TODO (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Maze (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Stack - Smart (3) State Machine (3) Streaming Algorithm (3) Subset Sum (3) Subtree (3) Transform Tree (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Search (3) bookkeeping (3) codebytes (3) Activity Selection Problem (2) Advanced Algorithm (2) AnAlgorithmADay (2) Application of Algorithm (2) Array Merge (2) BOJ (2) BT - Path Sum (2) Balanced Binary Search Tree (2) Bellman Ford (2) Binomial Coefficient (2) Bit Mask (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Branch and Bound Method (2) Clock (2) Codesays (2) Company - Baidu (2) Complete Binary Tree (2) DFS+BFS, Flood Fill (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-Output Solution (2) DP-Slide Window Gap (2) DP-i-k-j (2) DP-树形 (2) Distributed Algorithms (2) Divide and Conqure (2) Doubly Linked List (2) GoHired (2) Graham Scan (2) Graph - Bipartite (2) Graph BFS+DFS (2) Graph Coloring (2) Graph-Cut Vertices (2) Hamiltonian Cycle (2) Huffman Tree (2) In-order Traverse (2) Include or Exclude Last Element (2) Information Retrieval (2) Interview - Linkedin (2) Invariant (2) Islands (2) Knuth Shuffle (2) LeetCode - Recursive (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) MST (2) MST-Kruskal (2) Math-Remainder Queue (2) Matrix Power (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Palindromic (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) Shuffle (2) Sieve of Eratosthenes (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Stream (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Word Break (2) Word Graph (2) Word Trie (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - How To (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary Tree Variant (1) Bipartite (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Bug Free Code (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular Buffer (1) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Snapchat (1) Company-Yelp (1) Compression Algorithm (1) Concurrency (1) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS-Matrix (1) DP - Probability (1) DP Fill Diagonal First (1) DP-Difficult (1) DP-End with 0 or 1 (1) DP-Fill Diagonal First (1) DP-Graph (1) DP-Left and Right Array (1) DP-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Optimization (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) Database (1) Detect Negative Cycle (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Duplicate (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (1) Game (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) HOJ (1) Hanoi (1) Hard Algorithm (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Inorder-Reverse Inorder Traverse Simultaneously (1) Interpolation search (1) Interview (1) Interview - Easy (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Kosaraju’s algorithm (1) Kruskal (1) Kruskal MST (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode Diffcult (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Local MinMax (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Median (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Successor (1) Offline Algorithm (1) PAT (1) Parent-Only Tree (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) Probabilistic Data Structure (1) Proof (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Regular Expression (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie + DFS (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) Yahoo Interview (1) ZOJ (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts