LeetCode 3 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.

使用动态规划，分别计算前n个字符中以最后一个字符结尾的最长不重复子串，最后计算一下其中的最大值，时间复杂度为O(n*n+n)=O(n^2)。代码如下：

 1     public int lengthOfLongestSubstring(String s) {
 2         if(s.length() == 0){
 3             return 0;
 4         }
 5         int[] A = new int[s.length()];
 6         A[0] = 1;
 7         int max = 1;
 8         for(int i = 1; i< s.length(); i++){
 9             if(s.charAt(i) == s.charAt(i-1)){
10                 A[i] = 1;
11             }else{
12                 int j = 1;
13                 for(; j < A[i-1]+1; j++){
14                     if(s.charAt(i) == s.charAt(i-j)){
15                         break;
16                     }
17                 }
18                 A[i] = j;
19             }
20             if(max < A[i]){
21                 max = A[i];
22             }
23         }
24         return max;
25     }

参考源码：https://github.com/pkufork/Martians/blob/master/src/main/java/com/pkufork/martians/leetcode/L3_LongestSubstringWithoutRepeatingCharacters.java