[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)，代码如下：

	class Solution {
	public:
	/**
	* @param str: The scene string
	* @return: Return the length longest scene
	*/
	int getLongestScene(string &str) {
	int len = str.size(), res = 0;
	unordered_map<int, int> map;
	stack<pair<int, int>> st;
	for (int i = 0; i < len; ++i)
	{
	char c = str[i];
	if (map.find(c) == map.end())map[c] = i;
	else
	{
	int start = map[c];
	while (st.size() && st.top().second >= start)
	{
	start = min(st.top().first, start);
	st.pop();
	}
	st.emplace(start, i);
	res = max(res, i - start + 1);
	}
	}
	return res;
	}
	};

view raw The Longest Scene.cpp hosted with ❤ by GitHub