educative.io

Heads up: simpler more idiomatic solution (Java)

Courses
,
#1 
import java.util.*;
import java.util.stream.*;
public class Main{

    public static String minWindow(String s, String t) {
        // Write your code here
        String result = "";

        for (int end = 0, start = 0; end < s.length(); end++) {
            while(end - start + 1 >= t.length() && containsCharacters(s, start, end, t)) {
                if (result.length() == 0) {
                    result = s.substring(start, end+1);
                } else if (result.length() != 0 && s.substring(start, end+1).length() < result.length()) {
                    result = s.substring(start, end+1);
                }
                start++;
            }
        }
        return result;
    }

    public static boolean containsCharacters(String s, int start, int end, String t) {
        Deque<Character> order = new LinkedList<>();
        for (int i = 0; i <t.length(); i++) {
            order.add(t.charAt(i));
        }
        var sub = s.substring(start, end + 1);
        for (int i = 0; i <sub.length(); i++) {
            if (sub.charAt(i) == order.peek()) {
                order.poll();
            }
        }
        return order.isEmpty();
    }
}

Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Minimum Window Subsequence - Grokking Coding Interview Patterns in Java

#2

Hello Davide,

The solution you proposed is correct, however the time complexity of this solution is more complex as we can solve this problem in an easier way with less time complexity. This is important to keep a check on the time complexity to avoid complex solution.