--

leetcode 003: longest substring without repeating characters

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

---

---

problem:

---

  
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.

---

---

start code (c++)

---

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
    }
};

---

---

solution 1: 一次线性遍历，找到最大的子串的长度。 问题在于，我们需要在过去的子串中查找当前的char 的位置，最复杂的情况下，也就是这个字符串每个字母各不相同，那么将会用掉 n^2 但是问题在于，字符的总数是有限的，大概也就几百个，我们的复杂度会在 n 。

---

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty())
            return 0;
        
        int glbLongestStrSize = 1;
        int lclLongestStrSize = 1;
        int beg = 0;
        for (int end = 1; end < s.size(); end++){
            char c = s[end];
            int isub = beg;
            while (isub < end){
                if (s[isub] == c)
                    break;
                isub ++;
            }
            if (isub == end)
                lclLongestStrSize = end - beg + 1;
            else
                beg = isub + 1;
            
            if (lclLongestStrSize > glbLongestStrSize)
                glbLongestStrSize = lclLongestStrSize;
        }
        
        return glbLongestStrSize;
    }
};

---