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

algorithm, java, language-agnostic, string

Solution

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 ");
        }
    }
}

Problem

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.

Original source

Related problems