Saturday, November 7, 2015

minimum consecutive sub-string of S containing T

The problem is described from my friend Peng Li's blog:
http://allenlipeng47.com/PersonalPage/index/view/198/nkey

Given a random string S and another string T with unique elements,. find the minimum consecutive sub-string of S such that it contains all the elements in T
example:
S='
adobecodebanc'
T='
abc'
answer='banc"


We need a sliding window algorithm to solve this problem. The window data structure needs to tell us few things: 1)  are all characters in T found in the window? 2) how many times of each character found in the window appears so far? 3) if all characters are found in the window, can we shrink the window? 

To answer question 1 and 2, we can maintain a hashMap, its key is the character found, the value is the numbers of times the character appears in the window. 
To answer question 3, we need to maintain a data structure which can 1) represent the sliding window; 2) shrink the window if the number of first character in the window is more than once. We will use a Queue to do that, a double-ended queue actually in the below implementation. 

public static String miniSubstr(String s, String t){
        Deque<Item> q = new ArrayDeque<Item>();
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        int p=0, min=Integer.MAX_VALUE;
        String result = null;   
        while(p<s.length()){
            char c = s.charAt(p);
            if(t.indexOf(c)>-1){
                //update the sliding window
                q.add(new Item(c, p));   
                //update the counter map
                if(!map.containsKey(c))
                    map.put(c, 1);
                else
                    map.put(c, map.get(c)+1);   
                //shrink the sliding window if char in the head of q appears more than once
                while(true){
                    Item item = q.peek();
                    Integer num = map.get(item.c);
                    if(num>1){
                        q.removeFirst();
                        map.put(item.c, num-1);
                    }else
                        break;
                }
            }
           
            //when we find all characters, then we update result
            if(map.size() == t.length()){
                int current =  q.peekLast().p - q.peekFirst().p;
                if(current<min){
                    min = current;
                    result = s.substring(q.peekFirst().p, q.peekLast().p+1);
                }
            }
           
            p++;
        }       
        return result;
    }
   
    static class Item{
        char c;
        int p;
        Item(char c, int t){
            this.c = c; this.p = t;
        }
    }



No comments:

Post a Comment