Leetcode OJ #3 Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

题目： 找一个字符串的连续子串，使得该子串里不含相同字母，求符合条件的最长的子串的长度。

算法： DP----后缀思想

最初考虑过用二分答案，发现复杂度应该是O(n*n*log(n))，其中n*n验证一个答案对不对，log(n)是枚举可能答案的长度。然后就放弃，考虑DP

dp[i]：以str[i]结尾的符合条件的子串的最大长度。

那么dp[i]=  

(1)dp[i-1]+1  如果str[i]在str[i-dp[i-1]]~str[i-1]没有出现，

(2)i-j，其中，s[j] == s[i]，很容易发现从j+1~i必然符合"该子串里不含相同字母"的条件

ans = max(ans,dp[i-1],dp[i])，输出即可，比较坑的是，数组开1e5才不会爆，WA一次因为开的是1e4......

Leetcode 数据范围不给 这个很坑啊

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int dp[100001];
        //memset(dp,0,sizeof(dp));
        int ans = 0;
        for(int i=0;i<s.size();i++){
            dp[i]=0;
            if(i == 0){
                dp[i]=1;
                ans= max(ans,dp[i]);
                continue;
            }

            int flag=0;
            for(int j=i-dp[i-1];j<i;j++){
                if(s[j] == s[i]){
                    flag = 1;
                    dp[i]=max(dp[i],i-j);
                }
            }
            if(!flag)dp[i]=dp[i-1]+1;
            //ans = max(max(dp[i],dp[i-1]),ans);
            if(ans<dp[i])ans = dp[i];
            if(ans<dp[i-1])ans = dp[i-1];
        }
        //for(int i=0;i<s.size();i++){
        //    cout << i << "  " << dp[i] << endl;
        //}
        return ans;
    }
};

int main(){
    //freopen("5in.txt","r",stdin);
    Solution c;
    string in;
    while(cin >> in){
        cout << c.lengthOfLongestSubstring(in) << endl;

    }
    return 0;
}

后：看到有人根据有序，使用hash，O(n)方法可以做出来，并且因为字符在0-255，所以空间复杂度也降低了，学习了。转载自：

http://blog.csdn.net/xjtu0703/article/details/34083001

class Solution {
public:
    int arr[256];
    int lengthOfLongestSubstring(string s) {
		memset(arr,-1,sizeof(arr));
		int max=0,len=0;
		int length=s.size();
		for(int i=0;i<length;++i)
		{
			if(arr[s[i]]==-1)
			{
				arr[s[i]]=i;
				len++;
			}
			else
			{
				max=max>len?max:len;
				len=0;
				i=arr[s[i]];//设置下次迭代从repreating characters下标+1开始。
				memset(arr,-1,sizeof(arr));
			}
		}
		max=max>len?max:len;//防止最后的串没有进入else。
		return max;
    }
};

Leetcode OJ #3 Longest Substring Without Repeating Characters

原文：http://blog.csdn.net/u011026968/article/details/45604019