脸家面筋

双指针实现O(n):  左指针初始指向位置0，右指针from 1 to len(str), 左右指针所指字符相同则左指针右移，因为此时没必要保留左边的这个字符了，直到左右指针之间的子串包含所有的字符。

a   a   b   b   c
^  ^

a   a   b   b   c
    ^  ^

a   a   b   b   c
    ^        ^

a   a   b   b   c
    ^            ^

补充内容 (2016-9-12 16:42):
貌似不太对，呵呵。

could you provide more test cases?
sorted or not?
cbbaa return abbc
if not complicated, two pointer can solve in a sliding window way.
good luck.

可否问楼主是哪个学校的？

补充内容 (2016-9-11 21:02):
也想拿到面试

daddev 发表于 2016-9-11 14:36
双指针实现O(n):  左指针初始指向位置0，右指针from 1 to len(str), 左右指针所指字符相同则左指针右移，因 ...

这个不大对吧。
eg.
a a b b c b a
这样按照你的意思走了一遍之后会在b b c b a停了。
所以如果按照你的意思的话，是不是得要加个循环啊。

Josh 发表于 2016-9-10 12:15
先找出每个char最后一次出现的index，然后lo = 第一个最后出现的index
再找出每个char第一次出现的index， ...

比如还是用上面的例子。
a a b b c b a a a.
a: 0, 1, 6, 7, 8
b: 2, 3, 5
c: 4
所以lo:
a: 8
所以hi:
c: 4
感觉不work啊。
你能用例子解释一下你的思路吗？谢谢。

Josh 发表于 2016-9-9 23:15
先找出每个char最后一次出现的index，然后lo = 第一个最后出现的index
再找出每个char第一次出现的index， ...

这个做法好。
应该是时间O（n）,空间O（1）吧？
两个Map都是最多26个。
最后的return substring方法应该不在空间使用考量内。

难道不是two pointers线性扫一遍就出来了么

dhldxy 发表于 2016-9-12 02:24
这个不大对吧。
eg.
a a b b c b a

有道理。

jocelyna 发表于 2016-9-11 13:33
扫一遍用set记录出现的distinct字符数（min）， max = str.length（），遍历len from min to max（类似于sl ...

我觉得就是先扫一遍input string，取出所有distinct的字符组成一个target string，然后在原字符input string里找这个target的minimum window substring，除了一上来的预处理外，其他都和LC那道MWS一样，是这样吗？你也这么觉得？

dhldxy 发表于 2016-9-12 02:28
比如还是用上面的例子。
a a b b c b a a a.
a: 0, 1, 6, 7, 8

a a b b c b a a a.
a: 0, 1, 6, 7, 8
b: 2, 3, 5
c: 4
所以lo:
c: 4
接下来把lo之前的减掉，变成了：(a a b b ) c b a a a （括号里的被删了）
然后在扫一遍：
a: 6, 7, 8
b: 5
c: 4
所以hi:
a: 6
这样结果就是:cba
你应该没理解对吧