题目

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

---

Example1

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

Example2

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

Example3

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.

题目大意

在一个字符串重寻找没有重复字母的最长子串。

解题思路

这一题所用的思想是”滑动思想”,看了解析，和后面的第3,76,438,567题类似

滑动思想原理

滑动窗口的右边界不断的右移，只要没有重复的字符，就持续向右扩大窗口边界。一旦出现了重复字符，就需要缩小左边界，直到重复的字符移出了左边界，然后继续移动滑动窗口的右边界。以此类推，每次移动需要计算当前长度，并判断是否需要更新最大长度，最终最大的值就是题目中的所求。

代码一

package leetcode;

import java.util.HashMap;
import java.util.Map;

public class D03_LengthOfLongestSubstring {

    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> hashMap = new HashMap<>();
        int ans = 0;
        for (int end = 0, start = 0; end < s.length(); end++) {
            char alpha = s.charAt(end);
            if (hashMap.containsKey(alpha)) {
                start = Math.max(hashMap.get(alpha), start);
            }
            ans = Math.max(ans, end - start + 1);
            hashMap.put(s.charAt(end), end + 1);
        }
        return ans;
    }

}

复杂度分析

* 时间复杂度：O(N),其中N是字符串长度。
* 空间复杂度：O(N)。

代码二