Skip to content

727. Minimum Window Subsequence 👍

  • Time: $O(|\texttt{S}||\texttt{T}|)$
  • Space: $O(|\texttt{S}||\texttt{T}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  string minWindow(string S, string T) {
    const int m = T.length();
    const int n = S.length();
    // dp[i][j] := start index (1-indexed) of
    // the minimum window of T[0..i] and S[0..j)
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    // fill in placeholder values
    for (int j = 0; j <= n; ++j)
      dp[0][j] = j + 1;

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j)
        if (T[i - 1] == S[j - 1])
          dp[i][j] = dp[i - 1][j - 1];
        else
          dp[i][j] = dp[i][j - 1];

    int bestLeft = 0;
    int minLength = INT_MAX;

    for (int j = 1; j <= n; ++j)
      if (dp[m][j] > 0 && j - dp[m][j] + 1 < minLength) {
        bestLeft = dp[m][j] - 1;
        minLength = j - dp[m][j] + 1;
      }

    return minLength == INT_MAX ? "" : S.substr(bestLeft, minLength);
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public String minWindow(String S, String T) {
    final int m = T.length();
    final int n = S.length();
    // dp[i][j] := start index (1-indexed) of
    // the minimum window of T[0..i] and S[0..j)
    int[][] dp = new int[m + 1][n + 1];

    // fill in placeholder values
    for (int j = 0; j <= n; ++j)
      dp[0][j] = j + 1;

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j)
        if (T.charAt(i - 1) == S.charAt(j - 1))
          dp[i][j] = dp[i - 1][j - 1];
        else
          dp[i][j] = dp[i][j - 1];

    int bestLeft = 0;
    int minLength = Integer.MAX_VALUE;

    for (int j = 1; j <= n; ++j)
      if (dp[m][j] > 0 && j - dp[m][j] + 1 < minLength) {
        bestLeft = dp[m][j] - 1;
        minLength = j - dp[m][j] + 1;
      }

    return minLength == Integer.MAX_VALUE ? "" : S.substring(bestLeft, bestLeft + minLength);
  }
}
Back to top