Leetcode 727. Minimum Window Subsequence
Problem Explanation:
In this problem we are required to find the smallest substring (in terms of characters) of string S that contains all the characters of string T in order.
For example, consider we have two strings: S = "abcdebdde" and T = "bde". The smallest substring of S containing all characters of T in the correct order is "bcde"
Approach
The solution approach is using dynamic programming in the following way:
-
Create a 2-D Matrix of size
m+1 x n+1
, where m and n are lengths of strings T and S respectively, The valuedp[i][j]
in the matrix would represent the starting index of minimal window of substringT[0..i]
in the subsequenceS[0..j]
. -
Iterate through all the characters of T and S to fill this matrix. The matrix will be filled in a way that if
T[i]
is equal toS[j]
then the value atdp[i][j]
will bedp[i-1][j-1]
. -
After filling the whole matrix, simply iterate over the last row to find out the minimal length of the substring of S which is having the subsequence T.
Python Solution
1 2python 3class Solution: 4 def minWindow(self, s1: str, s2: str) -> str: 5 m = len(s2) 6 n = len(s1) 7 dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)] 8 for j in range(0, n+1): 9 dp[0][j] = j+1 10 for i in range(1, m+1): 11 for j in range(1, n+1): 12 dp[i][j] = dp[i][j-1] 13 if s2[i-1] == s1[j-1]: 14 dp[i][j] = dp[i-1][dp[i-1][j-1]] 15 best_left = 0 16 length = float('inf') 17 for j in range(1, n+1): 18 if dp[m][j] > 0 and j - dp[m][j] + 1 < length: 19 best_left = dp[m][j] - 1 20 length = j - dp[m][j] + 1 21 return "" if length==float('inf') else s1[best_left: best_left+length]
Java Solution
1 2java 3class Solution { 4 public String minWindow(String s1, String s2) { 5 int m = s2.length(), n = s1.length(); 6 int[][] dp = new int[m + 1][n + 1]; 7 for (int j = 0; j <= n; ++j) 8 dp[0][j] = j + 1; 9 for (int i = 1; i <= m; ++i) 10 for (int j = 1; j <= n; ++j) 11 if (s2.charAt(i - 1) == s1.charAt(j - 1)) 12 dp[i][j] = dp[i - 1][dp[i - 1][j - 1]]; 13 else 14 dp[i][j] = dp[i][j - 1]; 15 int bestLeft = 0; 16 int minLength = Integer.MAX_VALUE; 17 for (int j = 1; j <= n; ++j) 18 if (dp[m][j] > 0 && j - dp[m][j] + 1 < minLength) { 19 bestLeft = dp[m][j] - 1; 20 minLength = j - dp[m][j] + 1; 21 } 22 return minLength == Integer.MAX_VALUE ? "" : s1.substring(bestLeft, bestLeft + minLength); 23 } 24}
Javascript Solution
1 2javascript 3var minWindow = function(S, T) { 4 let m = T.length; 5 let n = S.length; 6 let dp = new Array(m + 1).fill().map(() => new Array(n + 1).fill(0)) 7 for (let j = 0; j <= n; ++j) 8 dp[0][j] = j + 1; 9 for (let i = 1; i <= m; ++i) 10 for (let j = 1; j <= n; ++j) 11 if (T.charAt(i - 1) === S.charAt(j - 1)) 12 dp[i][j] = dp[i - 1][dp[i - 1][j - 1]]; 13 else 14 dp[i][j] = dp[i][j - 1]; 15 let bestLeft = 0; 16 let minLength = Infinity; 17 for (let j = 1; j <= n; ++j) 18 if (dp[m][j] > 0 && j - dp[m][j] + 1 < minLength) { 19 bestLeft = dp[m][j] - 1; 20 minLength = j - dp[m][j] + 1; 21 } 22 return minLength === Infinity ? "" : S.substring(bestLeft, bestLeft + minLength); 23};
C++ Solution
1 2cpp 3class Solution { 4 public: 5 string minWindow(string S, string T) { 6 int m = T.size(); 7 int n = S.size(); 8 vector<vector<int>> dp(m + 1, vector<int>(n + 1)); 9 for (int j = 0; j <= n; ++j) 10 dp[0][j] = j + 1; 11 for (int i = 1; i <= m; ++i) 12 for (int j = 1; j <= n; ++j) 13 if (T[i - 1] == S[j - 1]) 14 dp[i][j] = dp[i - 1][dp[i - 1][j - 1]]; 15 else 16 dp[i][j] = dp[i][j - 1]; 17 int bestLeft = 0; 18 int minLength = INT_MAX; 19 for (int j = 1; j <= n; ++j) 20 if (dp[m][j] > 0 && j - dp[m][j] + 1 < minLength) { 21 bestLeft = dp[m][j] - 1; 22 minLength = j - dp[m][j] + 1; 23 } 24 return minLength == INT_MAX ? "" : S.substr(bestLeft, minLength); 25 } 26};
C# Solution
1 2csharp 3public class Solution { 4 public string MinWindow(string S, string T) { 5 int m = T.Length; 6 int n = S.Length; 7 int[][] dp = new int[m + 1][]; 8 for (int i = 0; i <= m; ++i) 9 dp[i] = new int[n + 1]; 10 for (int j = 0; j <= n; ++j) 11 dp[0][j] = j + 1; 12 for (int i = 1; i <= m; ++i) 13 for (int j = 1; j <= n; ++j) 14 if (T[i - 1] == S[j - 1]) 15 dp[i][j] = dp[i - 1][dp[i - 1][j - 1]]; 16 else 17 dp[i][j] = dp[i][j - 1]; 18 int bestLeft = 0; 19 int minLength = int.MaxValue; 20 for (int j = 1; j <= n; ++j) 21 if (dp[m][j] != 0 && j - dp[m][j] + 1 < minLength) { 22 bestLeft = dp[m][j] - 1; 23 minLength = j - dp[m][j] + 1; 24 } 25 return minLength == int.MaxValue ? "" : S.Substring(bestLeft, minLength); 26 } 27}
To provide a brief recap of the problem statement: We are required to find the smallest substring of a given string (S) that contains all the characters of another string (T) in order. After understanding the problem, we looked into the solution approach which involves creating a two-dimensional matrix and updating values based on the equality of characters from both strings.
The solution was then implemented in Python, Java, JavaScript, C#, and C++ respectively. Through each solution, we observe the dynamic programming approach of constructing a matrix. If the characters from both strings match at given indices, the current cell in the matrix is updated with the value of the preceding diagonal cell. After completing the matrix, it's the last row that holds the information about the minimal length of the substring of S containing the sequence T. The smallest window from S containing T is then identified.
Though the codes look different in terms of syntax, they all follow the same approach of applying dynamic programming for solving the problem. With enough practice, you will be able to write such solutions yourself! The key is to understand the problem, devise a solution strategy, and then implement it accurately in your programming language of choice.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.