Sliding Window - 3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

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

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"
Output: 1 Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3 Explanation: 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.

思路：

求字符串中最长不重复的字串，可以用一个hashmap来保存字符出现的下标，key是字符，value是下标（加一，这样是为了保证aab这种连续情况不会重复），应为这里key是单个字符所以可以用一个array代替，然后用两个指针，一个记录不重复字符开始位置，一个去探索字符串。

代码：

java：

class Solution {

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        int[] map = new int[256];
        int max = 0, start = 0;
        char[] strs = s.toCharArray();
        for (int i = 0; i < strs.length; i++) {
            if(map[strs[i]] > 0) {
                //already exist
                start = Math.max(start, map[strs[i]]);
            }
            map[strs[i]] = i + 1;   
            max = max > i- start + 1 ? max : i- start + 1;
        }
        
        return max;
    }
}