Longest Substring Without Repeating Characters

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.

1. public class T {  
2.     public static void main(String[] args) {  
3.         String s1 = "pwwkew";  
4.         String s2 = "abcabcbb";  
5.         String s3 = "dvdf";  
6.         String s4 = "bbbb";  
7.         System.out.println(lengthOfLongestSubstring(s1));  
8.   
9.     }  
10.   
11.     public static int lengthOfLongestSubstring(String s) {  
12.         int maxlength = 0;  
13.         int leftIndex = 0;  
14.         int rightIndex = 0;  
15.         while (rightIndex < s.length()) {  
16.             char target = s.charAt(rightIndex);  
17.             int mark = -1;  
18.             for (int i = leftIndex; i < rightIndex; i++) {  
19.                 if (s.charAt(i) == target) {  
20.                     mark = i + 1;  
21.                     break;  
22.                 }  
23.             }  
24.   
25.             if (mark != -1) {  
26.                 if ((rightIndex - leftIndex) > maxlength) {  
27.                     maxlength = (rightIndex - leftIndex);  
28.                 }  
29.                 leftIndex = mark;  
30.                 rightIndex = mark;  
31.   
32.             } else {  
33.                 rightIndex++;  
34.             }  
35.         }  
36.         if ((rightIndex - leftIndex) > maxlength) {  
37.             maxlength = (rightIndex - leftIndex);  
38.         }  
39.         return maxlength;  
40.     }  
41. }  

另附网上的答案一则.
http://www.cnblogs.com/grandyang/p/4480780.html

1. public class Solution {  
2.     public int lengthOfLongestSubstring(String s) {  
3.         int[] m = new int[256];  
4.         Arrays.fill(m, -1);  
5.         int res = 0, left = -1;  
6.         for (int i = 0; i < s.length(); ++i) {  
7.             left = Math.max(left, m[s.charAt(i)]);  
8.             m[s.charAt(i)] = i;  
9.             res = Math.max(res, i - left);  
10.         }  
11.         return res;  
12.     }  
13. } 
    

亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>