[刷题防痴呆] 0003 - 无重复字符的最大子串 (Longe

题目地址

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

题目描述

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.

思路

• 滑动窗口.
• 用一个 map 记录出现过的字符的位置.
• 同向双指针往前走不回退.

关键点

• 每次right往前走一步, count[sc[right]]++.
• 判断不重复的条件是while (count[sc[right]] > 1). 这种情况left一直往前走, 直到符合条件.
• 更新res 为Math.max(res, right - left + 1).
• 注意, count数组中的index应该对应的是字符, count[sc[right]].

代码

• 语言支持：Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null) {
            return 0;
        }
        int[] count = new int[256];
        char[] sc = s.toCharArray();
        int res = 0;
        for (int left = 0, right = 0; right < sc.length; right++) {
            count[sc[right]]++;
            while (count[sc[right]] > 1) {
                count[sc[left]]--;
                left++;
            }
            res = Math.max(res, right - left + 1);
        }

        return res;
    }
}