2014
03-21

# LeetCode-最长无重复字串[题解]

### Longest Substring Without Repeating Characters

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.

//============================================================================
// Name        : Longest.cpp
// Author      : coder
// Version     :
// Copyright   : www.acmerblog.com
// Description : Longest Substring Without Repeating Characters
//============================================================================

#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
int lengthOfLongestSubstring(string s) {
int hash[256];
for(int i=0; i<256; i++) hash[i] = -1;
int start = 0, ans = 0;
int i;
for(i=0; i<s.size(); i++){
if( -1 != hash[ s[i] ] ){
if(ans < i-start) ans = i-start;
for(int j=start; j<hash[ s[i] ]; j++) hash[j] = -1;
if(hash[  s[i] ] + 1  > start )
start = hash[ s[i] ] +1;
}
hash[ s[i]] = i;
}
if(ans < i-start) ans = i-start;
return ans;
}
};

int main() {
string str = "wlrbbmqbhcdarzowkkyhiddqscdxrjmowfrxsjybldbefsarcbynecdyggxxpklorellnmpapqfwkhopkmco";
str = "abcdbef";
Solution s ;
cout << s.lengthOfLongestSubstring(str) << endl;
return 0;
}

1. 第23行：
hash = -1是否应该改成hash[s ] = -1

因为是要把从字符串s的start位到当前位在hash中重置

修改提交后能accept，但是不修改居然也能accept

2. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。