Longest Substring Without Repeating Characters
- Total Accepted: 167158
- Total Submissions: 735821
- Difficulty: Medium
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.
解题思路参考自： http://www.geeksforgeeks.org/length-of-the-longest-substring-without-repeating-characters/
public class Num3 {
/*
* 方法一：暴力搜索，复杂度 O（n^3）
*/
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() == 0){
return 0 ;
}
String sub ;
for(int subLen = s.length() ; subLen > 0 ; subLen--){
for(int startIndex = 0 ; startIndex <= (s.length()-subLen) ; startIndex++){
//列出所有子串，然后判断子串是否满足有重复
if(startIndex != (s.length()-subLen)){
sub = s.substring(startIndex, startIndex+subLen) ;
}else{
sub = s.substring(startIndex) ;
}
if(!isRepeat(sub)){
return subLen ;
}
}
}
return 1 ;
}
private boolean isRepeat(String s){
for(int i = 1 ; i < s.length(); i++){
if(s.substring(i).contains(s.substring(i-1, i))){
return true ;
}
}
return false ;
}
/*
* 方法二：用hash的方法加上动态规划求解
*/
public int lengthOfLongestSubstring2(String s) {
if(s == null || s.length() == 0){
return 0 ;
}
int cur_len = 1 ; //lenght of current substring
int max_len = 1 ;
int prev_index ; // previous index
int [] visited = new int [256] ;
char [] arr = s.toCharArray() ;
/* Initialize the visited array as -1, -1 is used to
indicate that character has not been visited yet. */
for(int i = 0 ; i < 256 ; i++){
visited[i] = -1 ;
}
/* Mark first character as visited by storing the index
of first character in visited array. */
visited[arr[0]] = 0 ;
/* Start from the second character. First character is
already processed (cur_len and max_len are initialized
as 1, and visited[arr[0]] is set */
for(int i = 1 ; i < arr.length ; i++){
prev_index = visited[arr[i]] ;
/* If the current character is not present in the
already processed substring or it is not part of
the current NRCS, then do cur_len++ */
if(prev_index == -1 || i - cur_len > prev_index){
cur_len++ ;
}else{
/* Also, when we are changing the NRCS, we
should also check whether length of the
previous NRCS was greater than max_len or
not.*/
if(cur_len > max_len){
max_len = cur_len ;
}
// update the index of current character
cur_len = i - prev_index ;
}
visited[arr[i]] = i ;
}
// Compare the length of last NRCS with max_len and
// update max_len if needed
if (cur_len > max_len){
max_len = cur_len ;
}
return max_len ;
}
}