-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathquestion48.cpp
More file actions
34 lines (31 loc) · 1 KB
/
Copy pathquestion48.cpp
File metadata and controls
34 lines (31 loc) · 1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
假设字符串中只包含 ‘a’-‘z’ 的字符。
例如在字符串 “arabcacfr” 中，最长的不包含字符的子字符串是 “acfr”，长度为4。
Xiaobin Tian;
*/
#include<string>
using namespace::std;
int longestSubstring(string str){
int curlength = 0, maxlength = 0;
int *position = new int[26];
for(int i = 0; i < 26; ++i)
position[i] = -1;
for(int i = 0; i < str.size(); ++i){
int preIndex = position[str[i] - '0'];
if(preIndex < 0 || i - preIndex > curlength)
++curlength;
else{
if(curlength > maxlength)
maxlength = curlength;
curlength = i - preIndex;
}
position[str[i] - '0'] = i;
}
if(curlength > maxlength)
maxlength = curlength;
delete[] position;
return maxlength;
}