Wednesday, November 11, 2015

Find minimum string containing given pattern

Given two string input and pattern. Find minimum window in input which contains all characters from string pattern. E.g : Consider input as "axcerdndnfdkgdfgn" and pattern as "ngdf". Pattern can be found at two instances 8 -12 or 13-16 indices. So minimum sliding windows becomes 13-16.


If there is single instance then problem becomes simple but if there are multiple instances we would need minimum of those.

 
//Below code first find sliding windows then finds minimum of those.
class Solution {

    public  int startIndex;
    public  int min;
    public  int max;

    public boolean getSlidingWindow(String input, String pattern){
        max = -1;
        HashMap charSet = new HashMap();

        for(char ch : pattern.toCharArray()){
            charSet.put(ch, 0);
        }

        PriorityQueue pq1 = new PriorityQueue();

        int soFarCharacters = charSet.size();
        int count = startIndex;
        for (; count < input.length() ; count++){
            char ch = input.charAt(count);
            if(charSet.containsKey(ch)){
                int value = charSet.get(ch);
                if(value == 0){
                    charSet.put(ch, 1);
                    soFarCharacters--;
                }

                if(pq1.size() > 0 && input.charAt(pq1.peek()) == ch ){
                    pq1.poll();
                }
                pq1.offer(count);
                if(count > max) max = count;
            }
            if(soFarCharacters == 0)
                break;
        }
        startIndex = count;
        if(soFarCharacters == 0) {
            min = pq1.peek();
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        String input = "axcerdndnfdkgdfgn";
        String pattern = "ngdf";

        int start = 0;
        int end = input.length();
        boolean found = false;

        Solution sol = new Solution();
        sol.startIndex = 0;
        sol.min = input.length();
        sol.max = -1;

        while (sol.getSlidingWindow(input, pattern )){
            if(end - start > sol.max - sol.min){
                end = sol.max;
                start = sol.min;
            }
            found = true;
        }
        if(found)
            System.out.println("Minimum Sliding Window : " + start + " To " + end);
    }
}

//Output of above code
Minimum Sliding Window : 13 To 16

Question referenced from geeksforgeeks

No comments:

Post a Comment