[leetcode] 3 Longest Substring Without Repeating Characters

题目地址:https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

题目描述:Given a string, find the length of the longest substring without repeating characters. Examples: Given “abcabcbb”, the answer is “abc”, which the length is 3. Given “bbbbb”, the answer is “b”, with the length of 1. Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

我的代码:

class Solution { public: int lengthOfLongestSubstring(string s) { int n=s.size(); if(n<2)return n; int max=0; int start=-1; int a[200]; for(int i=0;i<200;i++)a[i]=-1; for(int i=0;i<n;i++){ if(a[s[i]]>start)start=a[s[i]]; a[s[i]]=i; if(i-start>max)max=i-start; } return max; } };

解题思路： 要求最长无重复连续子串，对于以位置i结束的子串而言，只需找到其前面最早出现重复的位置即可，利用动态规划，最早出现重复的位置有两种可能，一种是以i-1位置结束的最长字串里面有与i位置的字符相同的字符时，重复最早出现在该相同字符处，即前一个与i位置字符相同的字符处，另一种就是与i-1的重复位置相同。 因此，我们只需要两个变量，一个是前一个与i位置字符相同的字符的位置，这个可以用数组保存所有字符的最后出现位置，并同步更新，另一个就是i-1位置处的重复位置，就是我们需要的动态规划变量。