首页 > itarticle > leetcode 3. longest substring without repeating characters

leetcode 3. longest substring without repeating characters

admin 11月 11, 2020 0

题目

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

题解

设定两个指针l, r, 设定一个hash表，表示当前区间[l, r]中出现的字母的次数，每次r向右移动一位，当发现hash表中存在该字母时，移动l，并更新hash表，直到hash表中没出现过该字母，一直进行下去，直到r到达字符串结尾。

代码

class  {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> vis(256,0);
        int l = 0;
        int r = 0;
        int res = 0;
        while(r < s.size())
        {
            while(vis[s[r]] == 1)
            {
                vis[s[l]]--;
                l++;
            }
            vis[s[r]] = 1;
            r++;
            res = max(res,r - l);
        }
        return res;
    }
};