LongestSubstringWithoutRepeatingCharacters

Given a string, find the length of the longest substring without repeating characters.

创新互联是一家专业提供横山企业网站建设,专注与成都网站建设、网站设计、H5高端网站建设、小程序制作等业务。10年已为横山众多企业、政府机构等服务。创新互联专业网站设计公司优惠进行中。

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. } 
    

网页名称：LongestSubstringWithoutRepeatingCharacters
本文网址：http://shouzuofang.com/article/ppdddg.html