Python solution with detailed explanation


  • 0
    G

    Solution

    Minimum Window Substringhttps://leetcode.com/problems/minimum-window-substring/

    Algorithm

    • The key thing to note here is that characters in t are not supposed to be unique.
    • S = "aa". T = "aa" - Solution is "aa".
    • We keep two pointers start and end initialized to 0.
    • Now move the end pointer to the right unitl we find a solution.
    • When we find a solution, we try to optimize it - we move the start pointer as much as we can to right without breaking the constraints.
    from collections import Counter, defaultdict
    class Solution(object):
        def minWindow(self, s, t):
            """
            :type s: str
            :type t: str
            :rtype: str
            """
            st, c1, min_so_far, result, fmap = 0, Counter(t), len(s)+1, "", defaultdict(int)
            unique_ch = len(c1)
            for end in range(len(s)):
                if s[end] in c1:
                    fmap[s[end]] += 1
                    if fmap[s[end]] == c1[s[end]]:
                        unique_ch -= 1
                    while st <= end and unique_ch == 0:
                        if end - st + 1 < min_so_far:
                            min_so_far, result = end - st + 1, s[st:end+1]
                        if s[st] in fmap:
                            fmap[s[st]] -= 1
                            if fmap[s[st]] < c1[s[st]]:
                                unique_ch += 1
                        st += 1
            return result
    

    General Pattern to solve 2 pointer problems

    start, end = 0, len(input)
    // data-structures for your problem
    for end in range(len(input)):
        if input[end] contributes to extending the solution:
            update the impact of including input[end]
            while st <= end and input[st:end+1] is a valid solution:
                update for optimal solution
                update for the impact of removing input[start]
                start += 1
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.