76.md

76 Minimum Window Substring

Description

link

---

General Type

Substring Problems

---

Solution

• template as follow

    def findSubstring:
        hash_map = dict # most counter
        counter = 0 # check whether the substring is valid
        begin = end = 0 # two pointers, one point to tail and one  head
        sub_len = 0 # the length of substring

        for ... :  # initialize the hash map here

        while(end < len(s){

            if hash_map[s[end]] condition : # modify counter and hash_map here

            while( counter condition ){ 
                 
                # update sub_len here if finding minimum

                # increase begin to make it invalid/valid again
                
                if map[s[begin]] condition :  # modify counter here
            }  

            # update d here if finding maximum
        }
        return sub_len;
  }

---

Code

Complexity T : O(n)

class Solution:
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        cnt = collections.Counter(t)
        begin = end = head = 0
        sub_len, counter = float("inf"), len(t)

        while end < len(s):
            if cnt[s[end]] > 0:counter -= 1
            cnt[s[end]] -= 1
            while counter == 0:
                if end - begin < sub_len:
                    sub_len = end - begin
                    head = begin
                if cnt[s[begin]] == 0:counter += 1;
                cnt[s[begin]] += 1
                begin += 1
            end += 1
        return s[head:head + sub_len+1] if sub_len != float("inf") else ""

---

3 Longest Substring Without Repeating Characters

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        sets = set()
        begin = end = 0
        sub_len = 0

        while end < len(s):
            while s[end] in sets:
                sets.remove(s[begin])
                begin += 1
            sets.add(s[end])
            sub_len = max(sub_len,end - begin + 1)
            end += 1
        return sub_len

---

Longest Substring with At Most Two Distinct Characters

class Solution:
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        cnt = collections.defaultdict(int)
        begin = end = 0
        sub_len = 0
        
        while end < len(s):
            while cnt[s[end]] > 2:
                cnt[s[begin]] -= 1
                begin += 1
            sub_len = max(sub_len, end - begin + 1)
            cnt[s[end]] += 1
            end += 1
        
        return sub_len