Minimum Window Subsequence

This page explains Java solution to problem Minimum Window Subsequence using String data structure.

Problem Statement

Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequence of W.

If there is no such window in S that covers all characters in T, return the empty string "". If there are multiple such minimum-length windows, return the one with the left-most starting index.

Input: S = "abcdebdde", T = "bde"
Output: "bcde"
Explanation:
"bcde" is the answer because it occurs before "bdde" which has the same length.
"deb" is not a smaller window because the elements of T in the window must occur in order.

Solution

package com.vc.hard;

class MinimumWindowSubsequence {
    public String minWindow(String s, String t) {
        if(s == null || s.length() == 0 || t == null || t.length() == 0) return "";

        String ans = "";
        int ti = 0, si = 0, end = 0;
        while(si < s.length()) {
            if(s.charAt(si) == t.charAt(ti)) {
                ti++;
                if(ti == t.length()) {
                    ti--;
                    end = si + 1;
                    while(ti >= 0) {
                        if(t.charAt(ti) == s.charAt(si)) ti--;
                        si--;
                    }
                    ti++;
                    si++;
                    if(ans.equals("") || ans.length() > end - si) {
                        ans = s.substring(si, end);
                    }
                }
            }
            si++;
        }
        return ans;
    }
}

Time Complexity

O(S + (S / T)) Where
S is total number of characters in an input string
T is total number of characters in an input subsequence

Space Complexity

O(S) Where
S is total number of characters in an input string