Longest Substring Without Repeating Characters2015年6月9日

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

初步解决方法：

思路：把所有连续的子串找出来，再判断各个子串是否有重复元素

原字符串长度为n的话，所有子串的个数就是c(n,2) = n+n-1+...+1;

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        boolean reflag = false;
        int max = 0;
        List<String> lists = new ArrayList<String> ();
        for(int i=0; i<length; i++) {
            for(int j=i+1; j<length; j++) {
                lists.add(s.substring(i,j+1));
            }
        }
        
        for(String ssub : lists) {
            reflag = false;
            for(int i=0; i<ssub.length(); i++){
                char c =  ssub.charAt(i);
                if(ssub.indexOf(c,i+1)!=-1){
                    reflag = true;
                    break;
                }
            }
            
            if(!reflag){
                int sublen = ssub.length();
                if(sublen > max) {
                    max = sublen;
                }
            }
        }
        return max;
    }
    
}

View Code

    public static void main(String[] args) {
        String s = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&";
        boolean reflag = false;
        int max = 1;
        List<String> lists= new ArrayList<String>();
        int length = s.length();
        for(int i=0; i<length; i++) {
            for(int j=i+1; j<length; j++) {
                lists.add(s.substring(i, j+1));
            }
        }
        for(String subS:lists){
            reflag = false;
            for(int i=0; i<subS.length(); i++){
                char c = subS.charAt(i);
                if(subS.indexOf(c, i+1)!=-1){
                    reflag = true;
                    break;
                }
            }
            
            if(!reflag){
                int space = subS.length();
                if(space > max){
                    max = space;
                }
                
            }
            
            
        }
        System.out.println(max);
        System.out.println(lists.size());
        System.out.println(lists.toString());
    }

这种方法并不能通过leetcode的测试，但是逻辑上确实是正确的，对于特别长的字符串，会提示超时错误。

改进方法：

边查找子串边判断子串是否重复

1、依次查找长度为s.length--的所有子串，把相同长度的子串放在一个lists里面。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        boolean reflag = false;
        int max = 1;
        List<String> lists = new ArrayList<String> ();
        for(int len = length; len>1; len--){
            lists.clear();
            for(int i=0; i+len<=length; i++){
                lists.add(s.substring(i, i+len));
            }
            for(String ssub : lists) {
                    reflag = false;
                    for(int i=0; i<ssub.length(); i++){
                        
                        char c =  ssub.charAt(i);
                        if(ssub.indexOf(c,i+1)!=-1){
                           reflag = true;
                            break;
                        }
                    }
                    
                    if(!reflag){
                       return len;
                    }
            }
            
        }
        return max;
    }
    
}

2、依次查找长度为s.length--的所有子串，每查到一个就进行检测。

View Code

可惜以上两种方案仍然不能通过测试，超时报错！

无奈，在网上找到解决方法：

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = 0;
        String subString = new String();
        int[] indices = new int[s.length()];
        int lenSub = 0;
        int index = 0;
       //part1
        for (int i = 0; i < s.length(); i++) {
            int j = i;
            index = s.indexOf(s.charAt(i), ++j);
            if (index < 0) {
                index = s.length();
            }
            indices[i] = index;
        }
　　  　//part2
        for (int i = 0; i < indices.length; i++) {
            int index1 = i;
            int index2 = indices[i];
            if (index2 >= indices.length) {
                index2 = indices.length - 1;
            }
            lenSub = 0;
            for (; index2 != index1; index1++) {
                lenSub++;
                if (indices[index1] < index2) {
                    index2 = indices[index1];
                }
            }
            if (lenSub >= length) {
                length = lenSub;
            }
        }
　　　　//part3
        int lenSub1 = 0;
        for (int j2 = 0; j2 < indices.length; j2++) {

            if (indices[j2] == s.length())
                lenSub1++;
            else
                lenSub1 = 0;

        }
        if (lenSub1 > length)
            return lenSub1;
        else
            return length;
    }
}

上面这段代码可以分成三个部分看：

part1完成int[] indices的赋值操作,part2和part3其实是对应两种情况.

以字符串“aacdxdabcee”为例，代码执行过程如下

T代表10，B代表11
0 1 2 3 4 5 6 7 8 9 T
a a c d x d a b c e e
int[] indices:
1 6 8 5 B B B B B T B

i=0:
index1          0
index2          1
indeces[index1] 1
lensub          1

indexes[index1]和上一次循环的index2比较

i=1:
index1           1 2 3 4 5exit
index2           6 6 5 5 
indeces[index1]  6 8 5 B 
lensub           1 2 3 4

i=2:
index1           2 3 4 5exit
index2           8 5 5  
indeces[index1]  8 5 B  
lensub           1 2 3 

i=3:
index1           3 4 5exit
index2           5 5   
indeces[index1]  5 T   
lensub           1 2 

i=4:
index1           4 5 6 7 8 9 Texit
index2           T T T T T T
indeces[index1]  B B B B B T
lensub           1 2 3 4 5 6

....循环执行完length=6；


下面来看lensub1对应的循环
j2       4 5 6 7 8 9 T
lensub1: 1 2 3 4 5 0 1

对于上面这这种类型的字符串part1的长度肯定是大于part2的

但对于下面这种无重复的字符串就要依靠part2啦

0 1 2 3 4 5 
a b c d e f
int[] indices:
6 6 6 6 6 6

part2中这段代码的缘故
 if (index2 >= indices.length) {
         index2 = indices.length - 1;
 }
index2 被赋值为5
所以part2中循环执行完lensub也只被赋值到5

Longest Substring Without Repeating Characters2015年6月9日

推荐阅读