|
| 1 | +##What is window substring like |
| 2 | + |
| 3 | +``` |
| 4 | +S = "ADOBECODEBANC" |
| 5 | +T = "ABC" |
| 6 | +``` |
| 7 | + |
| 8 | +Minimum window is "BANC". A string with 1`A`, 1`B` and 1`C`. |
| 9 | + |
| 10 | +Something you shuold notice: |
| 11 | + |
| 12 | +* if a substring is a window string, it plus any string is also a window string. |
| 13 | + |
| 14 | +`ADOBEC` is a window string, so`ADOBECODE` is a window string too. |
| 15 | + |
| 16 | +* if a window string's left most or right most character, lets say`c`, is in`T` and the window string has more character`c` than`T` has, removing the`c` from the window string will not break that the remaining string is a window string. |
| 17 | + |
| 18 | +`ADOBECODEBA` has 2`A`, and more than`T` has (1`A`). so, after remove`A` from left or right, the string remains a window string (`ADOBECODEB` is a window string). |
| 19 | + |
| 20 | + |
| 21 | +##Loop invariant to find all possiable window string |
| 22 | + |
| 23 | +Assume that we had found a window string,`W`. |
| 24 | + |
| 25 | +Then |
| 26 | + |
| 27 | +1. When a new char comes,`W` + new char =`WN` is also a window. (Rule 1) |
| 28 | +1. Trim the new window string,`WN`, from the left part, remove any char that is redundant to have a window string. (Rule 2) |
| 29 | + |
| 30 | +Code looks like |
| 31 | + |
| 32 | +``` |
| 33 | +
|
| 34 | +W = a window string in S |
| 35 | +
|
| 36 | +foreach c after W in S |
| 37 | +
|
| 38 | + WN = W + c |
| 39 | +
|
| 40 | + // Trim left |
| 41 | +
|
| 42 | + foreach _c in WN |
| 43 | +
|
| 44 | + if _c can be remove from WN |
| 45 | + remove _c from the left part of WN |
| 46 | + else |
| 47 | + break |
| 48 | +
|
| 49 | + W = WN |
| 50 | +
|
| 51 | +``` |
| 52 | + |
| 53 | +###Finding the first`W` |
| 54 | + |
| 55 | +the`W` should have any char in`T`, this problem is like the`Check concatenation using count sum` in[Substring with Concatenation of All Words](../substring-with-concatenation-of-all-words). |
| 56 | + |
| 57 | +Use a map`need`, stores how many chars are needed. |
| 58 | + |
| 59 | +Use a map`seen`, stores how many chars are seen. |
| 60 | + |
| 61 | +Those maps are not only used in finding`W`, but also in triming redundant from`WN`. |
| 62 | + |
| 63 | + |
| 64 | +This last problem is when the`W` is found. |
| 65 | +Like[Substring with Concatenation of All Words](../substring-with-concatenation-of-all-words), just use a`counter`, |
| 66 | +When`seen` is added, just add 1 to the counter. |
| 67 | + |
| 68 | +The time`counter == T.length` is the time we first found`W`. |
| 69 | + |
| 70 | + |
| 71 | + |
| 72 | +_Note_: |
| 73 | +a char in`seen[c]` can contribute at most`need[c]` count to the`counter`. |
| 74 | + |
| 75 | + |
| 76 | + |
| 77 | + |
1 | 78 |
|
2 | | -##TODO |
3 | | -* write down thinking |
4 | 79 |
|