[LintCode]The Longest Scene

这道题可以转化为interval的问题，两个一样的字符和其中间的字符组成了一个scenne，scene如果有重合我们就merge取merge后最长的那一个。如果我们把scene看做interval，题目就转化成我们有不同的interval，如果interval有重合我们merge它们，求merge完之后左右新的interval中最长的那一个。对于多个相同的char我们只需要记录最左边的当起始位置start，然后每一次在curr遇见对应的char就形成了从start到curr的interval，中间的我们都不需要管因为被完全覆盖住了。我们从左向右扫，那么我们得到的interval是按照end index从小到大排列的。如果我们用stack记录所有merge之后的interval，每次我们遇到一个新的interval，我们check栈顶的interval看是否重合，是的话merge即可。这个做法有点类似Set Intersection Size at Least Two中去除被完全覆盖interval的做法。时间复杂度O(N)，每个interval最多进出stack一次。空间复杂度O(N)，代码如下：