leetcode-最长无重复子串

法一

剑指offer的思路是动态规划。

（1）用一个position数组(128)，存放所有字符最后一次出现的位置。

（2）用dp[i]表示以第i个字符结尾的无重复子串的最大长度：

如果第i个字符之前没有出现过，那么dp[i]=dp[i-1]+1

如果第i个字符之前出现过，那么就判断2个字符最近的距离d=i-position[ch]与dp[i-1]的关系

1）d<=dp[i-1]；dp[i]=d

2）d>dp[i-1]；dp[i]=dp[i-1]+1

（3）遍历dp数组求最值即可。

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

using namespace std;

int getloogestlen(const string &str)
{
    int len=str.size();
    if(len==0)
        return 0;
    int dp[len];
    memset(dp,0,sizeof(dp));

    int position[128];
    for(int i=0;i<128;i++)
    {
        position[i]=-1;
    }

    dp[0]=1;
    position[str[0]-0]=0;
    for(int i=1;i<len;i++)
    {
        int pos=str[i]-0;
        if(pos==-1)
            dp[i]=dp[i-1]+1;
        else   //出现过
        {
            int d=i-position[pos];
            if(d>dp[i-1])
                dp[i]=dp[i-1]+1;
            else
                dp[i]=d;
        }
        position[pos]=i;
    }
    int maxlen=-1;
    for(int i=0;i<len;i++)
    {
        if(maxlen<dp[i])
            maxlen=dp[i];
    }
    return maxlen;
}

int main()
{
    string str;
    cin>>str;
    int len=getloogestlen(str);
    cout<<len;
    return 0;
}

法二

跟动态规划的思路有点像。

（1）用position数组记录字符最后一次出现的位置

（2）用res来记录最长的长度，用left来记录局部无重复子串的起始位置

（3）遍历字符串，如果当前字符和局部起始字符一样，就把边界left加1。如果当前字符出现的位置在left前面，那么left就更新为当前字符出现的位置加1。然后更新res即可

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len=s.size();
        if(len==0)
            return 0;
        int a[128];
        fill(a,a+128,-1);
        int res=0;
        int left=0;
        for(int i=0;i<len;i++)
        {
            if(left==a[s[i]-0])
                left+=1;
            else if(left<a[s[i]-0])
                left=a[s[i]-0]+1;

            res=max(res,i-left+1);
            a[s[i]-0]=i;
        }
        return res;
    }
};