首页 > 代码库 > 算法--最长无重复字符子串
算法--最长无重复字符子串
转载请标明出处http://www.cnblogs.com/haozhengfei/p/d0906ebc98f7b6eaecb3ecd738dc78ac.html
最长无重复字符子串练习题
最长无重复字符子串练习
第12节 最长无重复字符子串练习题
对于一个字符串,请设计一个高效算法,找到字符串的最长无重复字符的子串长度。
给定一个字符串A及它的长度n,请返回它的最长无重复字符子串长度。保证A中字符全部为小写英文字符,且长度小于等于500。
测试样例:
"aabcb",5
返回:3
1
import java.util.*;
2
3
public class DistinctSubstring {
4
public int longestSubstring(String A, int n) {
5
//charPosition统计A中每种字符之前出现的位置
6
Map<Character, Integer> charPosition = new HashMap<Character, Integer>();
7
//preArr代表以s[i-1]结尾的情况下,最长无重复子串的长度
8
int[] preArr = new int[A.length()];
9
10
char[] str2charArr = A.toCharArray();
11
//从头到尾遍历str2charArr,统计出以每个字符为当前位置的向前最长无重复子串的长度
12
for(int i=0; i<A.length(); i++){
13
Integer lastPosOfChar = charPosition.get(str2charArr[i]);
14
if(lastPosOfChar == null){//说明当前字符第一次出现
15
//更新最长无重复子串的长度
16
preArr[i] = i == 0 ? 1 : preArr[i-1] + 1;
17
//记录当前字符出现的位置
18
charPosition.put(str2charArr[i], i);
19
}
20
else{//当前字符不是第一次出现(既然不是第一次出现,那也不是在第一个位置),也就是之前出现过该字符
21
//获取前一个字符最长无重复子串的长度
22
int aPos = lastPosOfChar + 1;
23
int unRepeatLen = preArr[i-1];
24
int bPos = i - unRepeatLen;
25
if(aPos >= bPos){
26
//当前位置的最长无重复子串长度
27
preArr[i] = i - aPos + 1;
28
}
29
else{
30
//当前位置的最长无重复子串长度
31
preArr[i] = i - bPos + 1;
32
}
33
//跟新当前字符出现的位置
34
charPosition.put(str2charArr[i], i);
35
}
36
}
37
//遍历preArr,最大值即为所求
38
int max = preArr[0];
39
for(int i: preArr) if(i > max) max = i;
40
41
return max;
42
}
43
}
您的代码已保存
答案正确:恭喜!您提交的程序通过了所有的测试用例
答案正确:恭喜!您提交的程序通过了所有的测试用例
算法--最长无重复字符子串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。