1 题目

剑指 Offer 48. 最长不含重复字符的子字符串

动态规划介绍：算法-动态规划-《算法导论3rd-P215》_hclbeloved的博客-CSDN博客

2 代码实现

2.1 从底向上的动态规划

class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        vector<int> dp(128,-1);//存储每个字符最后出现的位置
        int i=0,j=0,res=0;
        for(;j<s.size();j++)
        {    
            if(dp[s[j]]<i)//前面的子串不含新加的字符
                res=max(res,j-i+1);
            else//当前字符在之前的子串中出现过            
                i=dp[s[j]]+1;//更新i，使得i到j没有重复字符
            dp[s[j]]=j;//更改当前字符出现的位置                               
        }
        return res;
    }
};

2.2 滑动窗口

class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        unordered_set<char> w;
        int left = 0, right = 0, len = 0;
        while(right < s.length())
        {
            char c = s[right];
            if (w.count(c))
            {
                len = std::max(len, right - left);                
                w.erase(s[left++]);
                continue;
            }
            else
            {
                w.insert(c);
            }
            ++right;
        }

        len = std::max(len, right - left);
        return len;
    }
};