学步园

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length
of 1.

这个题是在LeetCode上面看到的。想到是用动态规划来做。但是具体如何推导没有想出来。

后来看了一下别人的思路，整理一下。写个总结。，

题意很简单，就是给定一个字符串，找到其中出现了的最长不重复子串。

比如abcc就是abc

abcdcdefg就是cdefg。

动态规划

我的动态规划一直学得比较挫。这里也是借他山之石。

int lengthOfLongestSubstring(string s)
{
	const int len = s.length();
	int *dp = new int[len+2];
	int last[256];
	for (int i = 0; i < 256; ++i) last[i] = len;
	dp[len] = len;

	for (int i = len - 1; i >= 0; --i)
	{
		dp[i] = min(dp[i+1], last[s[i]] - 1);
		last[s[i]] = i;
	}

	int ans = -1;
	for (int i = 0; i < len; ++i)
	{
		const int ret = dp[i] - i;
		ans = ans > ret ? ans : ret;
	}
	delete [] dp;
	return ans + 1;
}