Mock interview Nov. 10, 2020 10:00 PM

MinimumWindowSubsequence

Problem statement:
Given a string S and a string t , find the minimum window substring in S which contains all the characters of the string T in the same order.

import java.io.*;
import java.util.*;

class Solution {
  public static void main(String[] args) {
    
  }
}
  
                    ??
  f(i,j) = return j - i + 1, if j == len T  
           f(i+1,j+1) ,if T[j] == S[i]
           f(i+1,j)   , else
  
  S: abc
       i
  T: ab
              
       j
       T.Length -> 
  Let me propose dp[length + 1], dp[5] = 2, "found sbc subsequence, start position from 2"
      01234
    start index for each char in pattern "sbc" - largest one 
    s
      012345678
  s: "sbsssssbc", pattern string: "sssssbc", minimum length = 3
      i
              j
        *
      s:5 used:4 -> 4
      b:7
      c:8
      -> 
      s "s"
      b "sb"
      s "sbs"
      b "sbsb"
      c "sbsbc"  <- you should minimum length should be 3 -> found s, b, c, order is checked
      
   s: "sbsbcab", pattern string: "sbcb", minimum length = 5 "sbcab"
  
Input :
S : abbcabbacc   
    
 T:abcb 
  {a}     <-empty means found
  {a:1, b:3 c:1}

  a:0 b:0 c:0 ** to check if all values are <= 0 ----
    time O(S + T)
    space O(T's unique characters) ~ O(T)
    
  extend h until all characters are found
  inc l by 1 then extend h until all characeters are found
  
       maintain min 
T : abc, cba instead of abc, patten string abcb, substring should two b chars, c in between 
 
#1 naive : try all substrings of S O(S^3) <------  
#2 min window: O(S)

create a freq count map of T
a:0 b:-1 c:0
-----------  
a:0 b:0 c:0
  to check if all values are <= 0 ----

Output :
abbc - length=4

Interviewer hints and analysis:
  0123 
            "sbcb"  - meet b, dp[1], dp[3], four subproblems -> 
    
  "sbscbc"   "sbc" = 3
     2 
     0
   s - dp[1, 0] = 0, "s" subseqeunce start index
   b - dp[2, 1] = 0, "sb" 2 - work on "sbsbc", work on b
   s - dp[3, 0] = 2  "s", starting from third char -> short one
   
   dp[0] = 2
   b - dp[4, 1] = 2
   c - dp[5, 2] = 2 <- minimum length = 5 - 2 = 3
   
    return 
    

output would be 4 as that's the minimum length substring which contains all the characters of T in order.
  
  940. Distinct Subsequences II
    https://leetcode.com/problems/distinct-subsequences-ii/discuss/923642/First-practice-C-DP-%2B-GeeksForGeeks-%2B-DIY
 https://leetcode.com/discuss/interview-question/923693/google-phone-screen-find-shortest-substring-which-contains-all-the-alphabets-of-another-string/759913

distinct subsequence II