Problem
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb"
, the answer is "abc"
, which the length is 3.
Given "bbbbb"
, the answer is "b"
, with the length of 1.
Given "pwwkew"
, the answer is "wke"
, with the length of 3. Note that the answer must be a substring, "pwke"
is a subsequence and not a substring.
public class LengthOfSubstrings {
//第一种方法 暴力解决
/*public int lengthOfLongestSubstring(String s) {
int length = 0;
int lengthmax = 0;
String sub = "";
if (s == null) {
return 0;
}
sub+=s.charAt(0)+"";
lengthmax = 1;
length = 1;
for (int j = 1; j < s.length(); j++) {
for (int i = j; i < s.length(); i++) {
if (!sub.contains(s.charAt(i) + "")) {
length++;
sub += s.charAt(i);
}
if (lengthmax <= length) {
lengthmax = length;
}
}
}
return lengthmax;
}*/
//第二种方法:两个相同字符之间的字符串最短
/*
O(n)
用下标i,j表示子串
当j遇到重复的字符时,maxlen和j-i比较,并将exist中i-j之间重置为false,重新新的子串
否则 置为true 继续遍历
最后 比较 总长-i,max 排除某几个可能
*/
public int lengthOfLongestSubstring(String s) {
int s_length = s.length();
int j = 0;
int i=0;//i是子串的第一个位置,j是子串的最后一个位置
boolean exist[] = new boolean[256];//char类型有256个字符
int maxlength = 0;
while(j<s_length){
if(exist[s.charAt(j)]){
maxlength = Math.max(maxlength,j-i);
while(s.charAt(i)!=s.charAt(j)){
exist[s.charAt(i)]=false;
i++;
}
i++;
j++;
}else{
exist[s.charAt(j)]=true;
j++;
}
}
maxlength = Math.max(maxlength,s_length-i);
return maxlength;
}
}