Java BFS solution using prefix sum array. (43ms)


  • 0

    The idea is to first calculate the prefix sum array of each letter, 'a'~'z'.
    Then, using BFS to find the substrings from the longest length, the first one is the whole string s, and decrease the length by one via removing the head or tail.
    This way, we can assure that the first substring matches the condition is the longest one.
    Meanwhile, using a hash table for memorization to prevent from revisiting the same substring.

    public class Solution {
        boolean checkLetters(int[][] map, int s, int e, int k){
            int total = 0;
            for (int i=0; i<26; i++){ // check the count of each letter with in a substring
                int count = map[e][i] - map[s][i];
                if ( count > 0 && count < k ) return false; // if 0 means that this letter is not included
                total += count; // count the total letters
            }
            return total == (e-s); // the total letters should be equals to the length of this substring
        }
        
        boolean isVisited(Map<Integer, Set<Integer>> visited, int s, int e) {
            if (! visited.containsKey(s) ) return false;
            return visited.get(s).contains(e);
        }
        
        void addVisited(Map<Integer, Set<Integer>> visited, int s, int e) {
            if (! visited.containsKey(s) ) visited.put(s, new HashSet<Integer>());
            visited.get(s).add(e);
        }
        
        int BFS(int[][] map, int len, int k) {
            Stack<int[]> stack = new Stack<int[]>();
            Stack<int[]> temp = new Stack<int[]>();
            Map<Integer, Set<Integer>> visited = new HashMap<>();
            stack.push( new int[]{0,len} ); // the first substring is string s
            while ( ! stack.isEmpty() ) {
                int[] range = stack.pop(); // get start and end index of a substring
                if ( (range[1]-range[0]) >= k && ! isVisited(visited ,range[0],range[1]) )   {
                    if ( checkLetters(map, range[0], range[1], k) ) return range[1]-range[0];
                    addVisited(visited, range[0], range[1]);
                    temp.push( new int[]{range[0]+1,range[1]} ); // removing head
                    temp.push( new int[]{range[0],range[1]-1} ); // removing tail 
                }
                if (stack.isEmpty()) {
                    stack = temp;
                    temp = new Stack<int[]>();
                }
            }
            return 0;
        }
        public int longestSubstring(String s, int k) {
            if (s==null || s.length() == 0) return 0;
            int len = s.length();
            if (k > len) return 0;
            int[][] map = new int[len+1][26]; // prefix sum of 26 letters
            char[] cc =  s.toCharArray();
            for (int i=0; i < len ; i++ ){
                char c = cc[i];
                for (int j=0; j<26; j++) {
                    map[i+1][j] = map[i][j];
                }
                map[i+1][c-'a']++;
            }
            return BFS(map,len, k);
        }
    }
    

Log in to reply
 

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