# 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.```

```class Solution {
public int lengthOfLongestSubstring(String s) {
}
}```

`class Solution {    public int lengthOfLongestSubstring(String s) {        char[] charArray = s.toCharArray();        int len = charArray.length;        int longest = 0;        for (int i = 0; i < len; i++) {            for (int j = i + 1; j < len; j++) {                if (charArray[i] == charArray[j]) {                    if (longest < j - i) {                        longest = j - i;                    }                    i = j;                }            }        }        return longest;    }}`

```Submission Detail
41 / 983 test cases passed.
Submitted: 0 minutes ago
Input:
"c"
Output:
0
Expected:
1```

`class Solution {    public int lengthOfLongestSubstring(String s) {        char[] charArray = s.toCharArray();        int len = charArray.length;        int longest = 0;        int flag = 0;        for (int i = 0; i < len; i++) {            for (int j = i + 1; j < len; j++) {                if (charArray[i] == charArray[j]) {                    flag = 1;                    if (longest < j - i) {                        longest = j - i;                    }                    i = j;                }            }        }        if (flag == 0) {            longest = len;        }        return longest;    }}`

```Submission Detail
83 / 983 test cases passed.
Submitted: 0 minutes ago
Input:
"aab"
Output:
1
Expected:
2```

`// a b c a b e// 0 1 2 3 4 5//   i// j//     i// j j//       i// j j j//         i//   j j j`

i=1，j=0，最大子串长度longest=i-j+1=2

i=2，j=1，最大子串长度longest=i-j+1=2；j=0，最大子串长度longest=i-j+1=3>2；因此综合来看，此时最大子串长度为3

i=3，j=2，最大子串长度longest=i-j+1=2<3；j=1，最大子串长度longest=i-j+1=3=3；j=0，此时s[j]=s[i]，就没必要计算最大子串了（一定就是j=1的长度），但是更关键的一点，在下一轮循环i++的时候，j没必要遍历到j=0了，因为s[0]=s[3]，因此在有重复字符出现的时候，不计算最大子串长度，而是将j遍历的最小值变为相同字符时j的index值，这里就是1，下一轮循环开始j从i-1遍历到1即可

i=4，j=3，最大子串长度longest=i-j+1=2<3；j=2，最大子串长度longest=i-j+1=3=3；j=1，此时s[i]=s[j]，break，然后j的最小值变为1+1=2，下一轮循环j从i-1遍历到2

i=5，j=4，最大子串长度longest=i-j+1=2<3；j=3，最大子串长度longest=i-j+1=3=3；j=2，最大子串长度longest=i-j+1=4>3；此时结束，因此最大长度是4，子串也就是s[2]到s[5]，显然是正确的

`class Solution {    public int lengthOfLongestSubstring(String s) {        int index = 0, longest = 0;        int len = s.length();        char[] ss = s.toCharArray();        if (len == 0) {            return 0;        }        if (len == 1) {            return 1;        }        // a b c a b e        // 0 1 2 3 4 5        //   i        // j        //     i        // j j        //       i        // j j j        //         i        //   j j j        for (int i = 1; i < len; i++)        {            for(int j = i - 1; j >= index; j--)            {                if(ss[i] == ss[j])                {                    index = j + 1;                    break;                }                else                {                    if(longest < i - j + 1)                        longest = i - j +1;                }            }        }        return longest;    }}`

```Submission Detail
979 / 983 test cases passed.
Submitted: 0 minutes ago
Input:
"bbbbb"
Output:
0
Expected:
1```

`class Solution {    public int lengthOfLongestSubstring(String s) {        int index = 0, longest = 0;        int len = s.length();        char[] ss = s.toCharArray();        int sameNum = 0;        if (len == 0) {            return 0;        }        if (len == 1) {            return 1;        }        for (char a : ss) {            if (a == ss[0]) {                sameNum ++;            }        }        if (sameNum == len) {            return 1;        }        // a b c a b e        // 0 1 2 3 4 5        //   i        // j        //     i        // j j        //       i        // j j j        //         i        //   j j j        for (int i = 1; i < len; i++)        {            for(int j = i - 1; j >= index; j--)            {                if(ss[i] == ss[j])                {                    index = j + 1;                    break;                }                else                {                    if(longest < i - j + 1) {                        longest = i - j + 1;                    }                }            }        }        return longest;    }}`

```Submission Detail
983 / 983 test cases passed.
Status: Accepted
Runtime: 51 ms
Submitted: 0 minutes ago```

4月2日改进版

`package com.maoxiaomeng;/** * @author lihui * @date 2018/3/26 12:31 */class Solution {    public int lengthOfLongestSubstring(String s) {        int len = s.length();        if (len == 0) {            return 0;        }                int flag = 0;        for (int i = 0; i < len; i++) {            if (s.charAt(i) != s.charAt(0)) {                flag = 1;                break;            }        }                if (flag == 0 || len == 1) {            return 1;        }                int maxLen = 0;        int first = 0;                for (int i = 1; i < len; i++) {            for (int j = i - 1; j >= first; j--) {                if (s.charAt(i) == s.charAt(j)) {                    first = j + 1;                    break;                }                maxLen = Math.max(maxLen, i - j + 1);            }        }                return maxLen;    }}`

Leetcode上解决方法有人用hashset方式实现，比较顺眼

`class Solution {    public int lengthOfLongestSubstring(String s) {        //a b c b e        int maxLength = 0;        int len = s.length();        int left = 0, right = 0;        HashSet<Character> hashSet = new HashSet<>();        while(left < len && right < len){            if (hashSet.contains(s.charAt(right))){                hashSet.remove(s.charAt(left++));            } else {                hashSet.add(s.charAt(right++));                maxLength = Math.max(maxLength, right - left);            }        }        return maxLength;    }}`

`class Solution {    public int lengthOfLongestSubstring(String s) {        int maxLength = 0;        int length = s.length();        int i = 0, j = 0;        HashMap<Character, Integer> hashMap = new HashMap<>();        for (; j < length; ++j){            if (hashMap.containsKey(s.charAt(j))){                i = Math.max(hashMap.get(s.charAt(j)) + 1, i);            }            maxLength = Math.max(maxLength, j - i + 1);            hashMap.put(s.charAt(j), j);        }        return maxLength;    }}`