Thursday, August 6, 2020

Minimum Window SubString


Given a string S and a string T. Find the minimum window in S which contains all the characters in T with complexity O(n). Example, S = "ADOBECODEBANC", T = "ABC", Minimum window is "BANC".


public String minWindow(String s, String t) {
    HashMap goal = new HashMap<>();
    int goalSize = t.length();
    int minLen = Integer.MAX_VALUE;
    String result = "";
 
    //target dictionary
    for(int k=0; k map = new HashMap<>();
    for(int j=0; jgoal.get(s.charAt(i))){
                char pc = s.charAt(i);
                if(goal.containsKey(pc) && map.get(pc)>goal.get(pc)){
                    map.put(pc, map.get(pc)-1);
                }
 
                i++;
            }
 
            if(minLen>j-i+1){
                    minLen = j-i+1;
                    result = s.substring(i, j+1);
            }
        }            
    }
 
    return result;
}


No comments:

Post a Comment

Create a Digital Clock using HTML and JavaScript

Create a Digital Clock using HTML and JavaScript  <! DOCTYPE html> < html > < head > <...

Followers

Search This Blog

Popular Posts