脸家面筋

近期脸家，面试的时候脑抽，应该妥跪，来贡献一下面筋
美国小哥一上来先介绍了一下自己，然后就直接做题了
题目：最短连续子字符串
输入: "

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ith all characters in input，这个子字符串必须含有原字符串中的所有字符

先找出每个char最后一次出现的index，然后lo = 第一个最后出现的index
再找出每个char第一次出现的index， 然后hi = 最后一个第一次出现的index
结果就是 str[lo ... hi]

补充内容 (2016-9-10 12:20):
补充一下，第一步找出lo后把string lo以前的删掉，从 str[lo ...]开始进行第二步

Josh 发表于 2016-9-12 09:46
复杂度确实是一样的，应该区别不大吧，这个可能好跟面试官解释一点吧。可以说因为lo后面肯定会少一个char ...

这个做法怎么保证一定是最短的呢？
比如例子abcaabb:
第一遍
a: 0,3,4
b: 1,5,6
c: 2
按你的算法那lo＝2，扔掉了前面的ab
第二遍找caabb，结果是找到caab
但是最短的是abc啊？

双指针实现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):
貌似不太对，呵呵。

其实我觉得就是minimum window substring 的变种吧，扫一遍input string 得出所有 consecutive chars -> abc, then do a min window substring S=aabbc T=abc, output abbc

LZ我没看懂你的题是什么意思啊~可不可以讲清楚一点。

我也没看懂题意。。

不好意思  之前没有讲清楚
找出shortest continuous substring with all characters in input，这个子字符串必须含有原字符串中的所有字符

完全不知道题什么意思，最短的可以一个字符么？如果aabbccddeeffgghh....yzzz,也就最多去掉个a 和两个z？

题目没看懂啊，， 求具体再说一遍~

我觉得我没看懂lz题目,因为按照我理解,貌似线性搜索扫描一次就解决问题了

扫一遍用set记录出现的distinct字符数（min）， max = str.length（），遍历len from min to max（类似于sliding window一样遍历，同时从set中remove这个字符，如果set.size() == 0，说明是valid string， 此时return len）