2014
11-19

# LeetCode-Longest Substring Without Repeating Characters[贪心]

### 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.

\begin{center}
\includegraphics[width=300pt]{longest-substring-without-repeating-characters.png}\\
\figcaption{不含重复字符的最长子串}\label{fig:longest-substring-without-repeating-characters}
\end{center}

// LeetCode, Longest Substring Without Repeating Characters
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
int lengthOfLongestSubstring(string s) {
const int ASCII_MAX = 26;
int last[ASCII_MAX]; // 记录字符上次出现过的位置
int start = 0; // 记录当前子串的起始位置

fill(last, last + ASCII_MAX, -1); // 0也是有效位置，因此初始化为-1
int max_len = 0;
for (int i = 0; i < s.size(); i++) {
if (last[s[i] - 'a'] >= start) {
max_len = max(i - start, max_len);
start = last[s[i] - 'a'] + 1;
}
last[s[i] - 'a'] = i;
}
return max((int)s.size() - start, max_len);  // 别忘了最后一次，例如"abcd"
}
};


Java代码:

public class Solution {
public int lengthOfLongestSubstring(String s) {
int maxLen = 0;
int currentLen = 0;
int start = 0;
int hash[] = new int[256];
for(int i=0; i<s.length(); i++){
int lastPost = hash[ s.charAt(i) ];
if(lastPost == 0){
currentLen++;
}else{
for(int j=start; j< lastPost; j++)
hash[ s.charAt(j) ] = 0;
start = lastPost ;
currentLen = i - start + 1;
}
hash[s.charAt(i)] = i+1;
if(maxLen < currentLen) maxLen = currentLen;
}
return maxLen;
}
}