Case study: Mock interview Leetcode 727 Minimum window subsequence

 Here is the gist. 

	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

view raw MinimumWindowSubsequence hosted with ❤ by GitHub

Lessons learned from interviewee