剑指 Offer 48. 最长不含重复字符的子字符串 - 力扣（LeetCode）

剑指 Offer 48. 最长不含重复字符的子字符串 - 力扣（LeetCode）

思路：

最长子串要么包括最后一个字符，要么不包括最后一个字符。

我们可以设长度为i的包含最右侧字符的最长的串的长度为dp[i]

则当我们遍历到第i个字符时，我们可以获取上一次这个字符出现的位置（可以通过一个存储索引的数组实现），假设该位置为i。

1. 当i小于0时，说明前面没有出现过这个字符，因此 dp[i]=dp[i-1]+1

2. 当j-i>dp[i-1]时，说明i在dp[i-1]的最长串的左侧，因此 dp[i]=dp[i-1]+1 （因为长度不可能大于dp[i-1]+1，i到dp[i-1]最左侧之间肯定出现了和后面重复的字符）

3. 当j-i<=dp[i-1]时，说明i在dp[i-1]这个最长字串中间，因此 dp[i]=j-i

可以发现1和2两种情况可以合并：

所以得到递推式：

1. j-i>dp[i-1]:
   dp[i]=dp[i-1]+1
2. else:
   dp[i]=j-i;

int vis1[300];
int lengthOfLongestSubstring(string s) {
	int l1=0;
	int l2=0;
	int len=s.size();
	for (int i=0;i<130;i++)
	{
		vis1[i]=-1;
	}
	for (int i=0;i<len;i++)
	{
		int k=s[i]-'\0';

		int pos=vis1[k];
		vis1[k]=i;
		if (i-pos>l2)
		{
			l2++;
		}
		else{
			l2=i-pos;
		}
		if (l2>=l1)
			l1=l2;

	}
	return l1;
}