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 value dp[i][j] in the matrix would represent the starting index of minimal window of substring T[0..i] in the subsequence S[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 to S[j] then the value at dp[i][j] will be dp[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.