Breadth first search solution


  • 0
    C

    complexity O(n) since it's bounded by 26 characters.

    public class Solution {
        public int longestSubstring(String s, int k) {
            LinkedList<String>list = new LinkedList<>();
            list.add(s);
            int max = 0;
            int[] charMap;
            while(list.size()>0){
                LinkedList<String> tmpList = new LinkedList<>();
                for(String str : list){
                    charMap = new int[26];
                    char[] cary = str.toCharArray();
                    for(int i=0; i<cary.length; i++){
                        charMap[cary[i]-97]++;
                    }
                    boolean b = true;
                    for(int i=0; i<cary.length; i++){
                        if(charMap[cary[i]-97]<k){
                            cary[i]='-';
                            b = false;
                        }
                    }
                    str = new String(cary);
                    if(b) max = Math.max(str.length(), max);
                    else{
                        String[] splitAry = str.split("-");
                        for(int i=0; i<splitAry.length; i++){
                            if(splitAry[i].length()>max){
                                tmpList.add(splitAry[i]);
                            }
                        }
                    }
                }
                list = tmpList;
            }
            return max;
        }
    }
    

Log in to reply
 

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