The smallest window in line 1 containing all the characters from line 2 and the character from line 3

Question

Well, this is an interview question. And no, this is not a duplicate of this question .

Given 3 lines - str1 , str2 , str3 :

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

We need to find the minimal window in str1 that contains all the characters from str2 in any order, but not the character from str3 . In this case, the answer is: "strup" .

I came 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 this does not work for all test cases. This works for the example provided in this question. But when I sent the code, it failed for two test cases. No. I do not know test cases for which this failed.

Even after trying to enter various samples, I could not find a test case for which it fails. Can anyone take a look at what is wrong with the code? I would really appreciate if someone could give a better algorithm (only in pseudo-code). I know this is really not an optimized solution.

Answer 1

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

We are looking for a minimal substring from str1 that contains all str2 characters (supposedly ordered) , and no characters from str3 ..

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

The solution should be in the form of:

 str2.first XX .. XX str2.last 

So, to check this substring, we use the cursor over str2 , but we also have a restriction on the absence of str3 characters, so we have:

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

Goal Verification:

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

And for optimization, you can proceed to the next search option:

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

---

In case of str2 not ordered :

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

The solution should be in the form of:

 str2[x] XX .. XX str2[x] 

So, to check this substring, we use the str2 checklist, but we also have a restriction on the absence of 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 Verification:

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

And for optimization, you can proceed to the next search option:

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

Answer 2

Here is the working Java code tested in various test cases.

Basically, the algorithm uses a sliding window to view different windows within which the answer may lie. Each character in str2 is parsed no more than two times. Thus, the running time of the algorithm is linear, i.e. O(N) in the lengths of three lines. This is the most optimal solution to this problem.

 String str1 = "spqrstrupvqw"; String str2 = "sprt"; String str3 = "q"; char[] arr = str1.toCharArray(); HashSet<Character> take = new HashSet<Character>(); HashSet<Character> notTake = new HashSet<Character>(); HashMap<Character, Integer> map = new HashMap<Character, Integer>(); void run()throws java.lang.Exception{ System.out.println(str1 + " " + str2 + " " + str3); //Add chars of str2 to a set to check if a char has to be taken in O(1)time. for(int i=0; i<str2.length(); i++){ take.add(str2.charAt(i)); } //Add chars of str3 to a set to check if a char shouldn't be taken in O(1) time. for(int i=0; i<str3.length(); i++){ notTake.add(str3.charAt(i)); } int last = -1; int bestStart = -1; int bestLength = arr.length+1; // The window will be from [last....next] for(int next=last+1; next<arr.length; next++){ if(notTake.contains(arr[next])){ last = initLast(next+1); //reinitialize the window start. next = last; }else if(take.contains(arr[next])){ // take this character in the window and update count in map. if(last == -1){ last = next; map.put(arr[last], 1); }else{ if(!map.containsKey(arr[next])) map.put(arr[next], 1); else map.put(arr[next], map.get(arr[next])+1); } } if(last >= arr.length){ // If window is invalid break; } if(last==-1){ continue; } //shorten window by removing chars from start that are already present. while(last <= next){ char begin = arr[last]; // character is not needed in the window, ie not in set "take" if(!map.containsKey(begin)){ last++; continue; } // if this character already occurs in a later part of the window if(map.get(begin) > 1){ last++; map.put(begin, map.get(begin)-1); }else{ break; } } // if all chars of str2 are in window and no char of str3 in window, // then update bestAnswer if(map.size() == str2.length()){ int curLength = next - last + 1; if(curLength < bestLength){ bestLength = curLength; bestStart = last; } } } if(bestStart==-1){ System.out.println("there is no such window"); }else{ System.out.println("the window is from " + bestStart + " to " + (bestStart + bestLength-1)); System.out.println("window " + str1.substring(bestStart, bestStart+bestLength)); } } // Returns the first position in arr starting from index 'fromIndex' // such that the character at that position is in str2. int initLast(int fromIndex){ // clear previous mappings as we are starting a new window map.clear(); for(int last=fromIndex; last<arr.length; last++){ if(take.contains(arr[last])){ map.put(arr[last], 1); return last; } } return arr.length; } 

In addition, your code does not work in many trivial tests. One of them is str1 = "abc", str2 = "ab", str3 = "c".

PS. If you find it difficult to understand this code, try reading this simpler post , which is very similar to the given problem.

Answer 3

How to use regex?

 String regex = ".*((?=[^q]*s)(?=[^q]*p)(?=[^q]*r)(?=[^q]*t)[sprt][^q]+([sprt])(?<!ss|pp|rr|tt))"; Matcher m = Pattern.compile(regex).matcher("spqrstrupvqw"); while (m.find()) { System.out.println(m.group(1)); } 

This produces:

 strup 

This can also be wrapped in a method that dynamically generates a regular expression for variable inputs:

 import java.util.ArrayList; import java.util.List; import java.util.regex.Matcher; import java.util.regex.Pattern; public class MatchString { public static void main(String[] args) { System.out.println(getMinimalSubstrings("spqrstrupvqw", "sprt", "q")); System.out.println(getMinimalSubstrings("A question should go inside quotations.", "qtu", "op")); System.out.println(getMinimalSubstrings("agfbciuybfac", "abc", "xy")); } private static List<String> getMinimalSubstrings(String input, String mandatoryChars, String exceptChars) { List<String> list = new ArrayList<String>(); String regex = buildRegEx(mandatoryChars, exceptChars); Matcher m = Pattern.compile(regex).matcher(input); while (m.find()) { list.add(m.group(1)); } return list; } private static String buildRegEx(String mandatoryChars, String exceptChars) { char[] mandChars = mandatoryChars.toCharArray(); StringBuilder regex = new StringBuilder("[^").append(exceptChars).append("]*("); for (char c : mandChars) { regex.append("(?=[^").append(exceptChars).append("]*").append(c).append(")"); } regex.append("[").append(mandatoryChars).append("][^").append(exceptChars).append("]+([").append(mandatoryChars).append("])(?<!"); for (int i = 0; i < mandChars.length; i++) { if (i > 0) { regex.append("|"); } regex.append(mandChars[i]).append(mandChars[i]); } regex.append("))"); return regex.toString(); } } 

This produces:

 [strup] [quest] [agfbc, bfac]