---
# System prepended metadata

title: 'LeetCode #3 [Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)'
tags: [LeetCode, Medium, String]

---

###### tags: `LeetCode` `Medium` `String`
# LeetCode #3 [Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)
### (Medium)

給定一個字符串 s ，請你找出其中不含有重複字符的 最長子字串 的長度。

---
重點在於找到子字串的起始位置, 當dict[s[i]]>start時, 代表字串呈現這種情況 :
```
start.....s[i].....s[i]
```
此時之前所有的子字串都必須重頭開始計算(因為出現重複的了), 開始的位置為新的s[i]處。

若沒有發生dict[s[i]]>start, 則代表s[i]從來沒有出現, 或是出現在新的子字串起始點之前, 此時單純更新位置就好。

---
```
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> dict(256,-1);
        int cnt = 0;
        int start=-1;
        for(int i=0;i!=s.length();i++){
            if(dict[s[i]]>start)
                start=dict[s[i]];
            dict[s[i]]=i;
            cnt = max(cnt, i-start);
        }
        return cnt;
    }
};
```