FilesExpand file tree

 master

/

min_window_substr.py

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

44 lines (35 loc) · 1.37 KB

 master

/

min_window_substr.py

Top

File metadata and controls

• Code
• Blame

44 lines (35 loc) · 1.37 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

#!/usr/bin/env python

'''

Leetcode: Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,

S = "ADOBECODEBANC"

T = "ABC"

Minimum window is "BANC".

Note: If there is no such window in S that covers all characters in T, return the emtpy string "". If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

'''

from __future__ import division

import random

# O(|S|log|T|)

def min_window_substr(S, T):

if S == '' or T == '': return ''

last_seen = {}

start = 0; end = len(S)-1

T = set(T)

# find such a substring ended at i-th character.

for i, ch in enumerate(S):

if ch not in T: continue

last_seen[ch] = i

if len(last_seen) == len(T):

# all chars have been seen

first = min(last_seen.values()) #**We can use a priority queue, O(logn)

if i-first+1 < end-start+1:

start = first; end = i

window = S[start:end+1] if len(last_seen) == len(T) else ""

print window, len(window)

return window

if __name__ == '__main__':

print min_window_substr("AFDOBECODEBANCD", "ABCF")

print min_window_substr("AAABDFBFFHGKOAAFDOPPQDQPFVCCDEC", "ACD")

print min_window_substr("AAABBBB", "AB")

print min_window_substr("", "")