# Python, O(m) space complexity, almost O(n) time complexity

• Very brief explannation : m = len(T), n = len(S), scan string S and maintain a up to date list of start index of matching T in list dp(size of m), dp[i] denotes the start index when i+1 chars of T are matched. When T[i] appears in S, we simply update dp[i] = dp[i-1], when T[0] appears in S with index, we update dp[0] = index. Whenever dp[m-1] is updated, we have a new window that T is sub-sequence of, and we keep a running minimum of this window width

We scan S once, and each update depends the number of same char in T. The worst case is O(mn) when all position of T are identical. When the char in T doesn't have much repetition, O(n) time complexity is achieved.

Space complexity O(m)

``````class Solution(object):
def minWindow(self, S, T):
"""
:type S: str
:type T: str
:rtype: str
"""
n = len(S)
m = len(T)

dic = dict()
for i, s in enumerate(T):
dic.setdefault(s, []).append(i)

dp = [-1 for i in xrange(m)]

count = n+1
start = -1

for index, c in enumerate(S):
if c in dic:
for i in dic[c][::-1]:
if i == 0:
dp[i] = index
else:
dp[i] = dp[i-1]
if i == m-1 and dp[i] >= 0 and index - dp[i]+1 < count:
count = index - dp[i] + 1
start = dp[i]
if dp[-1] < 0:
return ""
return S[start:start+count]
``````

• java ver: 33ms, 97%

``````        int n = S.length(), m = T.length();
Map<Character, List<Integer>> c2is = new HashMap<>();
for (int i = 0; i < m; ++i) {
List<Integer> is = c2is.getOrDefault(T.charAt(i), new ArrayList<>());
c2is.put(T.charAt(i), is);
}
int[] dp = new int[m];
Arrays.fill(dp, -1);
int count = n + 1, start = -1;
for (int i = 0; i < n; ++i) {
char c = S.charAt(i);
List<Integer> is = c2is.get(c);
if (is == null) continue;
for (int j = is.size() - 1; j >= 0; --j) {
int k = is.get(j);
dp[k] = k == 0 ? i : dp[k - 1];
if (k == m - 1 && dp[k] >= 0 && i - dp[k] + 1 < count) {
count = i - dp[k] + 1;
start = dp[k];
}
}
}
return start < 0 ? "" : S.substring(start, start + count);
``````

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