InterviewBit : Window String

[congr]

https://www.interviewbit.com/problems/window-string/

Smallest Substring of All Characters
https://www.pramp.com/challenge/wqNo9joKG6IJm67B6z34

[congr]

The first Pramp question to ask peer. I couldn't solve it immediately.

Best article from leetcode.
https://articles.leetcode.com/finding-minimum-window-in-s-which/

[congr]

Hard to understand, but finally passed

public class Solution {
    
    public String minWindow(String S, String T) {
        if (S.length() < T.length()) return "";
        
        int N = S.length();
        int M = T.length();
        
        if (N == M && S.equals(T) == true) return T;
        else if (N == M && S.equals(T) == false) return "";
        
        int [] matching = new int[256];
        int [] pattern = new int[256];
        
        for (int i = 0; i < M; i++) {
            char c = T.charAt(i);
            pattern[c] ++;
        }
        
        int minLen = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int count = 0;
        boolean matched = false;
        for (int i = 0, j = 0; j < N; j++) {
            int index = S.charAt(j);
            
            if (pattern[index] > 0) {
                matching[index]++;
                
                if (matching[index] == pattern[index])
                    count += matching[index];
                    if (count == M) matched = true;
            }
            
            int x = S.charAt(i);
            while (i < j && matched && matching[x] >= pattern[x]) {
                if (pattern[x] < matching[x]) {
                    i++;
                    matching[x]--;
                } 
                else if (pattern[x] == 0)  
                    i++; 
                    
                else if (pattern[x] == matching[x]) break;
                
                if (minLen > j - i) {
                    start = i;
                    end = j;
                    minLen = end - start;
                }
                
                x = S.charAt(i);
            }
        }
        if (matched == false) return "";
        return S.substring(start, end+1);
    }
}

[congr]

Almost same solution on InterviewBit

public class Solution {
	public String minWindow(String S, String T) {
	    char s1[]=S.toCharArray();
		char s2[]=T.toCharArray();
		int countS2[]=new int[256];
		for(int i=0;i<s2.length;i++)
			countS2[s2[i]]++;
		
		int countS1[]=new int[256];
		int start=0;
		int count=0;
		int maxEnd=0;
		int maxStart=0;
		int minLength=Integer.MAX_VALUE;
		boolean found=false;
		for(int end=0;end<s1.length;end++)
		{
			char x=s1[end];
			
			if(countS1[x]<countS2[x])
				count++;
			
			countS1[x]++;
			
			if(count==s2.length)
			found=true;
		
			while(count==s2.length && countS1[s1[start]]>countS2[s1[start]])
			{
			    
				countS1[s1[start]]--;
				start++;
				if(end-start+1<minLength)
				{
    				maxEnd=end;
                    maxStart=start;			
					minLength=end-start+1;						
				}
				
			}
		}
		if(found)
		return S.substring(maxStart,maxEnd+1);
		
		return "";
		/*System.out.println(start+" "+maxEnd);*/
	}
}

[congr]

76. Minimum Window Substring
    https://leetcode.com/problems/minimum-window-substring/description/

class Solution {
    public String minWindow(String s, String t) {
        if (t.length() > s.length()) return "";
        
        HashMap<Character, Integer> map = new HashMap();
        int begin = 0, end = 0, head = 0, count = t.length();
        int diff = Integer.MAX_VALUE;

        for (Character c : t.toCharArray())
            map.merge(c, 1, Integer::sum);

        while (end < s.length()) {
            char e = s.charAt(end);

            if (map.containsKey(e) && map.merge(e, -1, Integer::sum) >= 0) { // t string
                count--;
            }

            while (count == 0) {
                if (diff > end - begin) {
                    head = begin;
                    diff = end - head;
                }

                char b = s.charAt(begin);
                if (map.containsKey(b) && map.merge(b, +1, Integer::sum) > 0) {// begin char is t string, then stop.
                    count++;
                }
                begin++;
            }
            end++;
        }

        if (diff == Integer.MAX_VALUE) return "";
        else return s.substring(head, head + diff + 1);
    }
}

[congr]

#307

[congr]

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";
        
        Map<Character, Integer> map = new HashMap();
        for (char c : t.toCharArray()) map.merge(c, -1, Integer::sum);
        
        int found = 0;
        int mLen = Integer.MAX_VALUE, mBegin = 0, mEnd = 0;
        char[] ch = s.toCharArray();
        for (int begin = 0, end = 0; end < s.length(); end++) {
            if (map.containsKey(ch[end]) && map.merge(ch[end], +1, Integer::sum) <= 0) found++;
            
            while(found == t.length()) {
                if (mLen > end - begin + 1) { // update
                    mBegin = begin;
                    mLen = end - begin + 1;
                }
                
                if (map.containsKey(ch[begin]) && map.merge(ch[begin], -1, Integer::sum) < 0) found--;
                begin++;
            }
        }
        
        if (mLen == Integer.MAX_VALUE) return "";
        return s.substring(mBegin, mBegin + mLen);
    }
}