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/
1 public class Num3 {
2 /*
3 * 方法一:暴力搜索,复杂度 O(n^3)
4 */
5 public int lengthOfLongestSubstring(String s) {
6 if(s == null || s.length() == 0){
7 return 0 ;
8 }
9 String sub ;
10 for(int subLen = s.length() ; subLen > 0 ; subLen--){
11 for(int startIndex = 0 ; startIndex <= (s.length()-subLen) ; startIndex++){
12 //列出所有子串,然后判断子串是否满足有重复
13 if(startIndex != (s.length()-subLen)){
14 sub = s.substring(startIndex, startIndex+subLen) ;
15 }else{
16 sub = s.substring(startIndex) ;
17 }
18 if(!isRepeat(sub)){
19 return subLen ;
20 }
21 }
22 }
23
24 return 1 ;
25 }
26
27 private boolean isRepeat(String s){
28 for(int i = 1 ; i < s.length(); i++){
29 if(s.substring(i).contains(s.substring(i-1, i))){
30 return true ;
31 }
32 }
33 return false ;
34 }
35
36 /*
37 * 方法二:用hash的方法加上动态规划求解
38 */
39 public int lengthOfLongestSubstring2(String s) {
40 if(s == null || s.length() == 0){
41 return 0 ;
42 }
43 int cur_len = 1 ; //lenght of current substring
44 int max_len = 1 ;
45 int prev_index ; // previous index
46 int [] visited = new int [256] ;
47 char [] arr = s.toCharArray() ;
48 /* Initialize the visited array as -1, -1 is used to
49 indicate that character has not been visited yet. */
50 for(int i = 0 ; i < 256 ; i++){
51 visited[i] = -1 ;
52 }
53 /* Mark first character as visited by storing the index
54 of first character in visited array. */
55 visited[arr[0]] = 0 ;
56
57 /* Start from the second character. First character is
58 already processed (cur_len and max_len are initialized
59 as 1, and visited[arr[0]] is set */
60 for(int i = 1 ; i < arr.length ; i++){
61 prev_index = visited[arr[i]] ;
62
63 /* If the current character is not present in the
64 already processed substring or it is not part of
65 the current NRCS, then do cur_len++ */
66 if(prev_index == -1 || i - cur_len > prev_index){
67 cur_len++ ;
68 }else{
69 /* Also, when we are changing the NRCS, we
70 should also check whether length of the
71 previous NRCS was greater than max_len or
72 not.*/
73 if(cur_len > max_len){
74 max_len = cur_len ;
75 }
76 // update the index of current character
77 cur_len = i - prev_index ;
78 }
79
80 visited[arr[i]] = i ;
81 }
82
83 // Compare the length of last NRCS with max_len and
84 // update max_len if needed
85 if (cur_len > max_len){
86 max_len = cur_len ;
87 }
88
89 return max_len ;
90
91 }
92
93 }