Leetcode 3 最长不重复字符串

题目

3. Longest Substring Without Repeating CharactersGiven a string, find the length of the longest substring without repeating characters.Example 1:
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.Example 3:
Input: "pwwkew"
Output: 3
Explanation: 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.

动态规划方法

其实就是f(n)=f(n-1)+1,但是需要加入一个限制 index - lastIndex

 class Solution {public int lengthOfLongestSubstring(String s) {int[] dp=new int[s.length()];if(s.length()== 0){ //空的时候“”return 0;}//dp[n]代表以数组下表为n位置结尾时 最长不重复子串，dp[0]=1,new dp[n]dp[0]=1;//只有一个元素 返回1int maxlength=1; //排除空的 最低1for(int i=1;i<s.length();i++){int j=i-1;while(j>=0&&s.charAt(j)!=s.charAt(i)){//j>=0j--;} //j就是前一个重复的字符串的index// 通过比较dp[i-1]+1,i-j的大小 就可以比较出来最后一个字符是否有重复//1、如果dp[i-1]+1>i-j,那么dp[i-1]+1有重复 选i-j//2、如果dp[i-1]+1<i-j,那么dp[i-1]+1没有重复 选dp[i-1]+1dp[i]=Math.min(dp[i-1]+1,i-j); // dp[j - 1] +1 =dp[j]maxlength=Math.max(maxlength,dp[i]);//找最大的}return maxlength;}
}

思路

1先把字符串长度为0，1时的情况列出来
2设变量j=1;j<s.size
用于遍历总体字符串的循环,当size=1时j的取值为0，因为当size的取值大于1时，j的取值应该为1才对，故j的初值取值为1；
3变量k=mark；k<j
（用于遍历不重复字符串的循环）不重复字符串最左边 mark，最右边j-1
4 设变量mark=0 mark的更新为k+1
（用于标志不重复字符串的初始值，在不重复字符串时若发现出现值相等的状况，则更新该mark的值为k+1）

举例：：abcad 已有不重复字符串abc 此时j=4 for（k=mark；k<4;k++）
当循环到k=0时出现相等的状况（此时设mark=k+1于是不重复字符串变为bca）（相当于舍去k时的那个重复的值）
5然后用j-mark更新当前max的值

class Solution {
public:int lengthOfLongestSubstring(string s) {if(s.size()==0){return 0;}if(s.size()==1){return 1;}int max=1;//用来更新最大值int j=1;//用来向前拓展字符串int mark=0;//用来标识不重复字符串的左，右侧用j--1标识while(j<s.size()){for(int k=mark;k<j;k++){if(s[k]==s[j]){mark=k+1;}}j++;if(j-mark>max){max=j-mark;}}return max;}
};