题意
如题,字符串只含a-z,输出该子串长度。例:"arabcacfr",输出4。
解题思路
递归思想
- 哈希表"int lastAppear[26]":存储各字母在之前遍历过程中最近一次出现的位置。初始化-1表示该字母从未出现。
- 变量len:为以每个字符结尾的最长不含重复字符的子串长度。计i-lastIdx为当前字符出现位置和上次出现该字符的位置之差。比较这两者:
- (1) 当i-lastIdx>len (以i-1结尾),说明字符出现在len 以(i-1结尾)对应的最长子串外,所以len=len+1。
- (2) i-lastIdx<=len (以i-1结尾),说明字符出现在len (以i-1结尾)对应的最长子串中,此时说明当前字符与上次出现的该字符之间无重复字符,所以len=i-lastIdx;
- 注意每次要更新哈希表。
用循环实现。
时间复杂度O(n).
代码(C++)
#include <iostream>
#include <string>
using namespace std;
int subStrLen(string s){
if(!s.size()){
return 0;
}
int lastAppear[26];
memset(lastAppear,-1,sizeof(lastAppear));
int tempLen=0;
int maxLen=0;
for(int i=0;i<s.size();++i){
if(i==0){
tempLen=1;
}
else{
int lastIdx=lastAppear[s[i]-'a'];
if(lastIdx==-1){
tempLen+=1;
}
else if((i-lastIdx)>tempLen){
tempLen+=1;
}
else{
tempLen=i-lastIdx;
}
}
lastAppear[s[i]-'a']=i;
if(tempLen>maxLen){
maxLen=tempLen;
}
}
return maxLen;
}
int main(int argc, const char * argv[]) {
string s="arabcacfr";
int len=subStrLen(s);
cout<<len<<endl;
return 0;
}
代码(Java)
public class Main {
public static void main(String args[]) {
String str="aa";
int len=getLongestSubDisStr(str);
System.out.println(len);
}
public static int getLongestSubDisStr(String str) {
if(str==null||str=="") {
return 0;
}
int[] map=new int[256];
int maxLen=-1;
int len=0;
for(int i=0;i<map.length;++i) {
map[i]=-1;
}
for(int i=0;i<str.length();++i) {
int lastIdx=map[str.charAt(i)];
if(lastIdx==-1||(i-lastIdx)>len) {
len+=1;
}
else {
len=i-lastIdx;
}
map[str.charAt(i)]=i;
if(len>maxLen) {
maxLen=len;
}
}
return maxLen;
}
}