Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Minimum window substring challenge

Sharing is caring!

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity \mathcal{O}(n).

Sample Input 0

S = "ADOBECODEBANC"
T = "ABC"

Sample Output 0

BANC

Solution
The first step we are going to take is, count the occurrences of each letter in string T. We will use a Map for that.

// Build a count map that holds how often each character in t appears
Map dict = new HashMap<>();
for (char c : t.toCharArray()) {
    if (dict.containsKey(c)) {
        dict.put(c, dict.get(c) + 1);
    } else {
        dict.put(c, 1);
    }
}

We then iterate over each character of string S using an iterator i and keep a count of characters encountered so far. Again, for that we will use a Map<Character, Integer> count. We will track the start and ending of the smallest substring using start and end. At first both, start and end are initialised to -1. As soon, as we hit a character that is contained in T we set start = i, as this is the soonest possible way that a substring may contain all characters in T.

While we are iterating over the letters in S, we check if we have collected all the required characters. As soon as that is the case, we set end = i. Now we have a substring that contains all the characters of T. But we are not done yet. Maybe there exists a smaller substring that also contains all the characters of T.

We continue iterating over the remaining characters in S while incrementing our end to i and adding them to count. If we hit a character that is equal to S[start] (the tail of the current substring) we remove it from the current substring. We also keep removing characters from the tail that are not contained in T or characters that are in T but we have in excess.

while (!dict.containsKey(tmp) || count.get(tmp) > dict.get(tmp)) {
    count.put(tmp, count.get(tmp) - 1);
    start++;
    tmp = s.charAt(start);
}

When we are done removing characters, we check if the new resulting substring is shorter than the previous one. If such is the case we update our answer.

The algorithm terminates when we have iterated over all characters in S.

The full implementations (two variations) are listed below.

Full code (Implementation 1)

while (!dict.containsKey(tmp) || count.get(tmp) > dict.get(tmp)) {
public class MinimumWindowSubstring {

    /**
     * 1) Build a count array count[] for string 2. The count array stores counts of characters. count['i'] = 1
     * count['t'] = 2 count['s'] = 1
     * 
     * 2) Scan the string1 from left to right until we find all the characters of string2. To check if all the
     * characters are there, use count[] built in step 1. So we have substring "this is a t" containing all characters
     * of string2. Note that the first and last characters of the substring must be present in string2. Store the length
     * of this substring as min_len.
     * 

* 3) Now move forward in string1 and keep adding characters to the substring "this is a t". Whenever a character is * added, check if the added character matches the left most character of substring. If matches, then add the new * character to the right side of substring and remove the leftmost character and all other extra characters after * left most character. After removing the extra characters, get the length of this substring and compare with * min_len and update min_len accordingly. *

* Basically we add 'e' to the substring "this is a t", then add 's' and then 't'. 't' matches the left most * character, so remove 't' and 'h' from the left side of the substring. So our current substring becomes "is a * test". Compare length of it with min_len and update min_len. *

* Again add characters to current substring "is a test". So our string becomes "is a test str". When we add 'i', we * remove leftmost extra characters, so current substring becomes "t stri". Again, compare length of it with min_len * and update min_len. Finally add 'n' and 'g'. Adding these characters doesn't decrease min_len, so the smallest * window remains "t stri". *

* 4) Return min_len. *

*

* Input string1: "this is a test string" Input string2: "tist" Output string: "t stri" * * @param s * @param t * @return */ public static String minWin(String s, String t) { Map targetMap = new HashMap(); char[] targetCharacters = t.toCharArray(); for (int i = 0; i < targetCharacters.length; i++) { Character c = targetCharacters[i]; if (targetMap.containsKey(c)) { targetMap.put(c, targetMap.get(c) + 1); } else { targetMap.put(c, 1); } } char[] sourceCharacters = s.toCharArray(); Map sourceMap = new HashMap(); int count = 0; int index = 0; for (int i = 0; i < sourceCharacters.length; i++) { Character c = sourceCharacters[i]; if (targetMap.containsKey(c)) { if (sourceMap.containsKey(c)) { // str = AABC, target = ABC ==> That way we don't increment count // when targetMap.containsKey('A') is fulfilled twice for the 2 'A's. if (sourceMap.get(c) < targetMap.get(c)) { count++; } sourceMap.put(c, sourceMap.get(c) + 1); } else { sourceMap.put(c, 1); count++; } } if (count == t.length()) { index = i; break; } } StringBuilder sb = new StringBuilder(); sb.append(s.substring(0, index + 1)); int minLen = sb.length(); String window = sb.toString(); for (int i = index + 1; i < sourceCharacters.length; i++) { char c = sourceCharacters[i]; sb.append(c); if (sourceMap.containsKey(c)) { sourceMap.put(c, sourceMap.get(c) + 1); } else { sourceMap.put(c, 1); } if (c == sb.charAt(0)) { // remove extra characters int tmp = 0; char tmpChar = sb.charAt(tmp); while (!targetMap.containsKey(tmpChar) || (targetMap.containsKey(tmpChar) && sourceMap.get(tmpChar) > targetMap.get(tmpChar))) { if (targetMap.containsKey(tmpChar) && sourceMap.get(tmpChar) > targetMap.get(tmpChar)) { sourceMap.put(tmpChar, sourceMap.get(tmpChar) - 1); } tmp++; tmpChar = sb.charAt(tmp); } if (sb.substring(tmp, sb.length()).length() <= minLen) { window = sb.substring(tmp, sb.length()); sb.replace(0, sb.length(), window); minLen = window.length(); } } } return window; } public static void main(String[] args) { System.out.println(minWin("ADOBECODEBANC", "ABC")); System.out.println(minWin("this is a test string", "tist")); } }

Full code (Implementation 2)

public class MinimumWindowSubstring2 {

    public static String minWin(String s, String t) {
        String ans = "";

       // Build a count map that holds how often each character in t appears
        Map dict = new HashMap<>();
        for (char c : t.toCharArray()) {
            if (dict.containsKey(c)) {
                dict.put(c, dict.get(c) + 1);
            } else {
                dict.put(c, 1);
            }
        }


        Map count = new HashMap<>();
        int n = s.length();
        int start = -1;
        int end = -1;
        boolean complete = false;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);

            if (start == -1 && dict.containsKey(c)) {
                // Detected first character included in target string
                start = i;
            }

            // Added current character to count
            if (count.containsKey(c)) {
                count.put(c, count.get(c) + 1);
            } else {
                count.put(c, 1);
            }

            // Check if we have all required characters
            if (!complete) {
                complete = true;
                for (Character key : dict.keySet()) {
                    if (count.containsKey(key)) {
                        if (count.get(key) < dict.get(key)) {
                            complete = false;
                            break;
                        }
                    } else {
                        complete = false;
                        break;
                    }
                }
            }

            if (complete) {
                end = i;
            }

            char tmp = s.charAt(start);
            if (complete && tmp == s.charAt(i)) {
                while (!dict.containsKey(tmp) || count.get(tmp) > dict.get(tmp)) {
                    count.put(tmp, count.get(tmp) - 1);
                    start++;
                    tmp = s.charAt(start);
                }
            }

            if (ans.isEmpty() || (end - start) < ans.length()) {
                ans = s.substring(start, end + 1);
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        System.out.println(minWin("ADOBECODEBANC", "ABC"));
        System.out.println(minWin("this is a test string", "tist")); // t stri

    }
}