Accepted Java Solution


  • 0
    S
    import java.util.Hashtable;
    public class Solution {
    
        public String minWindow(String s, String t)  {
            int n = s.length();
            int m = t.length();
            if(n==0 || m==0)
                return "";
            char [] chars = t.toCharArray(); //we first convert the target string to a character array
            HashSet<Character> charSet = new HashSet<>(); //this set is meant to hold all the distinct characters in the target string
            Hashtable<Character, Integer> charMap = new Hashtable<>(); //this hashtable is meant to hold all the characters and their count
            HashSet<Character> visited = new HashSet<>(); //this is meant to store all the characters that are contained in the current string
            PriorityQueue<Integer> indices = new PriorityQueue<>(); //this is meant to hold the indices of the characters in the source string                                                                     that match characters in the target string
            //populating the hashtable
            for(char c: chars) {
                charSet.add(c);
                if(!charMap.containsKey(c)) 
                    charMap.put(c, 1);
                else 
                    charMap.put(c, charMap.get(c)+1);
            }  
            int min = Integer.MAX_VALUE; //minimum substring length
            String res =""; //substring 
            int i = 0; //start
            int j = 0; //end
            while(j < n && i<n) {
                char c= s.charAt(j);
    
                if(charMap.containsKey(c)) { //current character belongs in target string
                    charMap.put(c, charMap.get(c)-1); //decrement count
                    if(charMap.get(c)==0) { //if I've found all needed instances of this character add it to visited characters
                        visited.add(c);
                    }
                    indices.offer(j); //record its index
                    i = indices.peek(); //record the start as the minimum index of all characters in the substring
                }
                if(visited.size()==charSet.size()) { //if i've found all characters of target string
    
                    while(!indices.isEmpty()) { //shrink substring to contain only needed characters only
                        int k = indices.peek();
                        char ch = s.charAt(k);
                        charMap.put(ch, charMap.get(ch)+1);
                        if(charMap.get(ch) > 0) { //we find the first character that is not redundant
                            visited.remove(ch);
                            String str = s.substring(k, j+1); //the minimum substring starts at the index
                            res = str.length() < min? str: res;
                            min = str.length() < min? str.length() : min;
                            break;
                        }
                        else indices.poll();
                    }
                    if(!indices.isEmpty())
                        indices.poll(); //remove the index of that character to start looking for another minimum susbtring
                    if(!indices.isEmpty())
                        i = indices.peek();
                }
    
                j+=1;
            }
            return res;
            
        }
    }
    

Log in to reply
 

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