3. Longest Substring Without Repeating Characters

題目原文

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
             Note that the answer must be a substring, "pwke" is a subsequence
             and not a substring.

解題思路

1. 從第一筆資料開始找，第一次遇到的都放進容器。

2. 計算所有不重複的item長度為何。

3. 如果遇到重複過的item，則從該item第一次遇到的時候開始往下計算不重複的長度。

程式解答

class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        std::map<char, int> p;
        std::map<char, int>::iterator it; 
        int size = s.length();
        int length = 0;
        
        for (int j = 0, i = 0; j < size; j++) 
        {
            if ((it = p.find(s[j])) != p.end()) 
                i = std::max(it->second, i);
            p[s[j]] = j + 1;
            length = std::max(length, j - i + 1);
        }
        return length;
    }
};