Minimum window in String 1 containing all characters from String 2 and no character from String 3

Question

Ok, this is an interview question. And no it's not a duplicate of this question.

Given 3 strings - str1, str2, str3:

str1 = "spqrstrupvqw"
str2 = "sprt"
str3 = "q"

We've to find the minimum window in str1, which contains all characters from str2 in any order, but no character from str3. In this case the answer would be: "strup".

I've come up with this code:

static String minimumWindow(String str1, String str2, String str3) {

        class Window implements Comparable<Window> {
            int start;
            int end;

            public Window(int start, int end) {
                this.start = start;
                this.end = end;
            }

            public int getEnd() {
                return end;
            }

            public int getStart() {
                return start;
            }

            public int compareTo(Window o) {
                int thisDiff = end - start;
                int thatDiff = o.end - o.start;

                return Integer.compare(thisDiff, thatDiff);
            }

            @Override
            public String toString() {
                return "[" + start + " : " + end + "]";
            }
        }

        // Create Sets of characters for "contains()" check

        Set<Character> str2Chars = new HashSet<>();
        for (char ch: str2.toCharArray()) {
            str2Chars.add(ch);
        }

        Set<Character> str3Chars = new HashSet<>();
        for (char ch: str3.toCharArray()) {
            str3Chars.add(ch);
        }

        // This will store all valid window which doesn't contain characters
        // from str3.
        Set<Window> set = new TreeSet<>();

        int begin = -1;

        // This loops gets each pair of index, such that substring from 
        // [start, end) in each window doesn't contain any characters from str3
        for (int i = 0; i < str1.length(); i++) {
            if (str3Chars.contains(str1.charAt(i))) {
                 set.add(new Window(begin, i));
                 begin = i + 1;
            }
        }

        int minLength = Integer.MAX_VALUE;
        String minString = "";

        // Iterate over the windows to find minimum length string containing all
        // characters from str2
        for (Window window: set) {
            if ((window.getEnd() - 1 - window.getStart()) < str2.length()) {
                continue;
            }

            for (int i = window.getStart(); i < window.getEnd(); i++) {
                if (str2Chars.contains(str1.charAt(i))) {
                      // Got first character in this window that is in str2
                      // Start iterating from end to get last character
                      // [start, end) substring will be the minimum length
                      // string in this window
                     for (int j = window.getEnd() - 1; j > i; j--) {
                        if (str2Chars.contains(str1.charAt(j))) {
                            String s = str1.substring(i, j + 1);

                            Set<Character> sChars = new HashSet<>();
                            for (char ch: s.toCharArray()) {
                                sChars.add(ch);
                            }

                            // If this substring contains all characters from str2, 
                            // then only it is valid window.
                            if (sChars.containsAll(str2Chars)) {
                                int len = sChars.size();
                                if (len < minLength) {
                                    minLength = len;
                                    minString = s;
                                }
                            }
                        }
                    }
                }
            }
        }

    // There are cases when some trailing and leading characters are
    // repeated somewhere in the middle. We don't need to include them in the
    // minLength. 
    // In the given example, the actual string would come as - "rstrup", but we
    // remove the first "r" safely.
        StringBuilder strBuilder = new StringBuilder(minString);

        while (strBuilder.length() > 1 && strBuilder.substring(1).contains("" + strBuilder.charAt(0))) {
            strBuilder.deleteCharAt(0);
        }

        while (strBuilder.length() > 1 && strBuilder.substring(0, strBuilder.length() - 1).contains("" + strBuilder.charAt(strBuilder.length() - 1))) {
            strBuilder.deleteCharAt(strBuilder.length() - 1);
        }

        return strBuilder.toString();
    }

But it doesn't work for all the test cases. It does work for the example given in this question. But when I submitted the code, it failed for 2 test cases. No I don't know the test cases for which it failed.

Even after trying various sample inputs, I couldn't find a test case for which it fails. Can someone take a look as to what is wrong with the code? I would really appreciate if someone can give a better algorithm (Just in pseudo-code). I know this is really not the optimized solution though.

Answer 1

str1 = "spqrstrupvqw"
str2 = "sprt"
str3 = "q"

We're looking for the minimum sub-string from str1 that contain all str2 characters (assume ordered) and no characters from str3 ..

i = 1 .. str1.length
cursor = 1 .. str2.length

The solution must be on the form:

str2.first X X .. X X str2.last

So to check for that sub-string we use a cursor over str2, but we also have the constraint of avoiding str3 characters, so we have:

if str3.contain(str1[i])
    cursor = 1
else
    if str1[i] == str2[cursor]
        cursor++

Goal check is:

if cursor > str2.length
    return solution
else
    if i >= str1.length
        return not-found

And for optimization, you can skip to the next look-ahead which is:

look-ahead = { str2[cursor] or { X | X in str3 }}

---

In case str2 is not ordered:

i = 1 .. str1.length
lookup = { X | X in str2 }

The solution must be on the form:

str2[x] X X .. X X str2[x]

So to check for that sub-string we use a check-list str2, but we also have the constraint of avoiding str3 characters, so we have:

if str3.contain(str1[i])
    lookup = { X | X in str2 }
else
    if lookup.contain(str1[i])
        lookup.remove(str1[i])

Goal check is:

if lookup is empty
    return solution
else
    if i >= str1.length
        return not-found

And for optimization, you can skip to the next look-ahead which is:

look-ahead = {{ X | X in lookup } or { X | X in str3 }}

---

Code

class Solution
{
    private static ArrayList<Character> getCharList (String str)
    {
        return Arrays.asList(str.getCharArray());
    }

    private static void findFirst (String a, String b, String c)
    {
        int cursor = 0;
        int start = -1;
        int end = -1;

        ArrayList<Character> stream = getCharList(a);
        ArrayList<Character> lookup = getCharList(b);
        ArrayList<Character> avoid = getCharList(c);

        for(Character ch : stream)
        {
            if (avoid.contains(ch))
            {
                lookup = getCharList(b);
                start = -1;
                end = -1;
            }
            else
            {
                if (lookup.contains(ch))
                {
                    lookup.remove(ch)

                    if (start == -1) start = cursor;

                    end = cursor;
                }
            }

            if (lookup.isEmpty())
                break;

            cursor++;
        }

        if (lookup.isEmpty())
        {
            System.out.println(" found at ("+start+":"+end+") ");
        }
        else
        {
            System.out.println(" not found ");
        }
    }
}