Longest Substring Without Repeating Characters(LeetCode)

文章目录

1. 1. Question:Longest Substring Without Repeating Characters
2. 2. SourceCode:
   1. 2.1. s1
   2. 2.2. s2

Question: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.

SourceCode:

s1

//笔者提交版本；耗时：14ms；
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = 0;
        //边界控制
        if(null == s||s.isEmpty()||"".equals(s)){
            return len;
        }
        if(1 == (len = s.length())){
            return len;
        }
        
        //可以走到这里说明最少有一个子串，用result存放最大长度
        int result = 1;
        //用来存放最长子串
        StringBuilder sb = new StringBuilder(len);
        sb.append(s.charAt(0));
        
        //遍历s，与最长子串比较
        for(int i = 1; i<len ;i++){
            char obj = s.charAt(i);
            int sbLen = sb.length();
            int j = sbLen-1;
            //用obj 检查 最长子串中是否已存在 字符 obj，如果存在，那么此时的子串已经到头了，可以结束了
            //我们要开始寻找下一个子串了，故需要把重复的字符obj和其之前的的字符都删除。
            for(;j>=0;j--){
                if(obj == sb.charAt(j)){
                    sb.delete(0,j+1);
                    break;
                }
            }
            
            //刚遍历的字符obj 加入到sb中；
            sb.append(obj);
            sbLen = sb.length();
            result = result < sbLen ? sbLen : result;
        }
        
        return result;
    }
}

s2

//该版本参考了Discuss,还没看Discuss；耗时：ms；
//待写