'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List


class Solution:
    # two pointers
    '''
    * we can conduct two steps by using two pointers for this probelm:
     * 1. check feasibility from left to right
     * 2. check optimization from right to left
     * we can traverse from left to right, find a possible candidate until 
     reach the first ending character of T
     * eg: for the string s = abcdebdde and t = bde, we should traverse s string 
     until we find first e, i.e. abcde, then traverse back from current "e" to 
     find if we have other combination of bde with smaller length.
     * right: fast pointer that always points the last character of T in S
     * left: slow pointer that used to traverse back when right pointer 
     find the last character of T in S
     * tIndex: third pointer used to scan string T
     * minLen: current minimum length of subsequence
    '''
    def minWindow1(self, S: str, T: str) -> str:
        right = 0
        minLen = float("inf")
        result = ""
        
        while right < len(S):
            tIdx = 0
            # use fast pointer to find the last character of T in S
            while right < len(S):
                if S[right] == T[tIdx]:
                    tIdx += 1
                if tIdx == len(T):
                    break
                right += 1
            # if right pointer is over than boundary
            if right == len(S):
                break
            # use another slow pointer to traverse from right to left until 
            # find first character of T in S
            left = right
            tIdx = len(T) - 1
            while left >= 0:
                if S[left] == T[tIdx]:
                    tIdx -= 1
                if tIdx < 0:
                    break
                left -= 1
            # if we found another subsequence with smaller length, update result
            if right - left + 1 < minLen:
                minLen = right - left + 1
                result = S[left:right+1]
            # we have to move right pointer to the next position of left 
            # pointer, NOT the next position of right pointer
            right = left + 1
        return result
            
        
    
    # LTE, brute force
    def minWindow(self, S: str, T: str) -> str:
        if not S or not T: return ""
        
        def match(s1, s2):
            pt1 = pt2 = 0
            l1, l2 = len(s1), len(s2)
            while pt1 < l1 and pt2 < l2:
                if s1[pt1] == s2[pt2]:
                    pt1 += 1
                    pt2 += 1
                else:
                    pt1 += 1
            if pt2 < l2:
                return False
            else:
                return True
        
        cands = []
        nt, ns = len(T), len(S)
        l = nt
        while l <= ns:
            for idx in range(ns - l + 1):
                substring = S[idx:idx+l]
                # print (substring)
                if match(substring, T):
                    # print (substring, T)
                    cands.append((idx, substring))
            if cands:
                break
            else:
                l += 1
        cands.sort(key = lambda x: (len(x[1]), x[0]))
        return cands[0][1] if cands else ""
        
                    