Leetcode

1 flashcards · Programming Languages · by Akhil Umesh Mehendale

1. 727. Minimum Window Subsequence Hard 406 16 Favorite Share 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 sa…

   class Solution { static const bool debug = false; public: string minWindow(string S, string T) { int Slen = S.size(); int Tlen = T.size(); vector<vector<int>> dp(Tlen, vector<int>(Slen, -1)); dp[0][0] = T[0] == S[0] ? 0 : -1; for(int j = 1; j < Slen; j++) { dp[0][j] = T[0] == S[j] ? j : dp[0][j-1]; } for(int i = 1; i < Tlen; i++) { for(int j = i; j < Slen; j++) { if(S[j] == T[i]) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = dp[i][j-1]; } } int min_len = INT_MAX; int min_idx = -1; for(int i = 0; i <…