【LeetCode】#3——Longest Substring Without Repeating Characters

03-06

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

Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", 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.
翻譯：

給定一個字元串，找到最長的子串的長度沒有重複字元。

實例：

「abcabcbb」，答案是「ABC」，它的長度是3。

「bbbbb」，答案是「B」，長度為1。

「pwwkew」，答案是「wke」，以3的長度。注意，答案必須是一個字元串，「pwke」是子串。

解決：

class Solution {

public:

int lengthOfLongestSubstring(string s) {

int a[128];//存數字元下標

int start = 0;

int len = 0;

for(int i = 0 ;i < 128 ; i++)

a[i] =- 1;

for(int i = 0; i < s.size(); ++ i){

if(a[s[i]] >= start){//該字元出現過

if(i-start > len)

len = i-start;

start = a[s[i]] + 1; //忽略該位置以前的字元

}

a[s[i]] = i;//更新當前字元的下標

}

if(len > s.size() - start)

return len;

else

return s.size() - start;

}

};