Leetcode 76. Minimum Window Substring

https://leetcode.com/problems/minimum-window-substring/

Finding first substring is not difficult, while the key is how to go on.

Solution:

# T:O(n) S:O(k)
class Solution:
    # @return a string
    def minWindow(self, S, T):
        current_count = [0 for i in xrange(52)]
        expected_count = [0 for i in xrange(52)]
        # count characters in T
        for char in T:
            expected_count[ord(char) - ord('a')] += 1
        i, count, start, min_width, min_start = 0, 0, 0, float("inf"), 0
        while i < len(S):
            current_count[ord(S[i]) - ord('a')] += 1
            # only count characters in T and do not count too many repeated
            if current_count[ord(S[i]) - ord('a')] <= expected_count[ord(S[i]) - ord('a')]:
                count += 1
            if count == len(T):
                # now we found a substring, ready to record and go on
                # the first part means the start char is not in T so we can remove it
                # the second part means the start char is in T but it is redundant
                # if start char in T and necessary, this sentence will not be executed until another occurs
                while expected_count[ord(S[start]) - ord('a')] == 0 or\
                      current_count[ord(S[start]) - ord('a')] > expected_count[ord(S[start]) - ord('a')]:
                    current_count[ord(S[start]) - ord('a')] -= 1
                    start += 1
                if min_width > i - start + 1:
                    min_width = i - start + 1
                    min_start = start
            i += 1   
        if min_width == float("inf"):
            return ""
        return S[min_start:min_start + min_width]

Run Time: 324 ms