Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/727.html

727. Minimum Window Subsequence

Level

Hard

Description

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.

Example 1:

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.

Note:

• All the strings in the input will only contain lowercase letters.
• The length of S will be in the range [1, 20000].
• The length of T will be in the range [1, 100].

Solution

If S and T are equal, then simply return S.

Use sliding window. If a substring W of S exists such that T is a subsequence of W, then a substring of S that is longer than or have the same length as W must also exist. Therefore, find such a substring of S starting from index 0 in S and index 0 in T. If the last character of T is reached, then the current index in S is the end index of the substring, and find the maximum possible start index of the substring in S. After the start index and the end index are found, the minimum window size can be updated, and store the start index and the end index as well. Then set the index in T to 0 and try to find another substring in S. Repeat the process until the end of S is reached.

After all the characters in S are visited, the minimum substring length can be obtained, and return the shortest substring. If the length still equals to S.length(), then such a substring does not exist, so return an empty string.

• Java

• class Solution {
      public String minWindow(String S, String T) {
          if (S.equals(T))
              return S;
          int sLength = S.length(), tLength = T.length();
          int start = 0, end = sLength - 1;
          int sIndex = 0, tIndex = 0;
          while (sIndex < sLength) {
              if (S.charAt(sIndex) == T.charAt(tIndex))
                  tIndex++;
              if (tIndex == tLength) {
                  int rightIndex = sIndex;
                  tIndex--;
                  while (tIndex >= 0) {
                      if (S.charAt(sIndex) == T.charAt(tIndex))
                          tIndex--;
                      sIndex--;
                  }
                  sIndex++;
                  if (rightIndex - sIndex < end - start) {
                      start = sIndex;
                      end = rightIndex;
                  }
                  tIndex = 0;
              }
              sIndex++;
          }
          int windowSize = end - start + 1;
          if (windowSize == sLength)
              return "";
          else
              return S.substring(start, start + windowSize);
      }
  }
  

All Problems

All Solutions