Leetcode 3. Longest Substring Without Repeating Characters

佚名 6年前 (2019-04-24) 随笔 1016人围观抢沙发百度已收录

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

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        /*
        动态规划
        dp[k]为以k为结尾的最长无重复子串
        last_index[x]是x上一次出现的位置,若未出现过即为-1
        dp[k]=min(dp[k-1]+1,k-last_index[s[k]])
        
        边界条件:
        1.输入为空，直接输出0
        2.dp[0]=1,循环从1开始
        */
        #include<algorithm>
        using namespace std;
        if(s.empty()) return 0;
        int last_index[130];
        //init
        for(int i=0;i<130;++i) last_index[i]=-1;
        vector<int> dp(s.size(),1);//dp[0]=1
        last_index[s[0]]=0;
        int ans=1;
        //
        for(int k=1;k<s.size();++k){
            dp[k]=min(dp[k-1]+1,k-last_index[s[k]]);
            last_index[s[k]]=k;
            ans=max(ans,dp[k]);
        }
        return ans;
    }
};