lintcode: 最长无重复字符的子串

时间:2022-05-23 23:30:55

题目

最长无重复字符的子串给定一个字符串,请找出其中无重复字符的最长子字符串。

例如,在"abcabcbb"中,其无重复字符的最长子字符串是"abc",其长度为 3

对于,"bbbbb",其无重复字符的最长子字符串为"b",长度为1

解题

利用HashMap,map中不存在就一直加入,存在的时候,找到相同字符的位置,情况map,更改下标

public class Solution {
/**
* @param s: a string
* @return: an integer
*/
public int lengthOfLongestSubstring(String s) {
// write your code here
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
if(s == null)
return 0;
if(s.length() <=1)
return s.length();
int longest = -1;
for(int i = 0;i<s.length();i++){
char ch = s.charAt(i);
if(map.containsKey(ch)){
longest = Math.max(map.size(),longest);
i = map.get(ch);
map.clear();
}else{
map.put(ch,i);
}
}
longest = Math.max(map.size(),longest);
map.clear();
return longest;
}
}

利用数组来判断该元素是否已经存在过

public class Solution {
/**
* @param s: a string
* @return: an integer
*/
public int lengthOfLongestSubstring(String s) {
// write your code here
if(s == null)
return 0;
if(s.length() <=1)
return s.length();
int longest = -1;
int start = 0;
boolean[] flag = new boolean[256];
char[] arr = s.toCharArray();
for(int i =0;i< arr.length;i++){
char cur = arr[i];
if(flag[cur]){
longest = Math.max(longest,i - start);
for(int k = start;k<i;k++){
if( arr[k] == cur){
start = k + 1;
break;
}
flag[arr[k]] = false;
}
}else{
flag[cur] = true;
}
}
longest = Math.max(longest,arr.length - start);
return longest;
}
}