Leetcode 3.Longest Substring Without Repeating Characters

27 Apr 2018

Reading time ~1 minute

Leetcode 3.Longest Substring Without Repeating Characters

题目：

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

示例：

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.

这题的思路是用两个指针指向字符串，如果没有重复情况，右指针向右移动，左指针不动，如果出现重复，左指针向左移动直至没有出现重复。维护一个set（数组可以更简单）来确定是否出现重复。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.length() == 1) {
            return 1;
        }
        
        Set<Character> set = new HashSet();
        char[] chars = s.toCharArray();
        int m = 0, n = 0, max = 1;
        
        for (n = 0; n < chars.length; n++) {
            
            if (set.contains(chars[n])) {
                if (max < n - m) {
                    max = n - m;
                }
                while (chars[m] != chars[n]) {
                    set.remove(chars[m]);
                    m++;
                }
                m++;
            } else {
                set.add(chars[n]);
            }
        }
        return Math.max(max, n - m);
    }
}

Leetcode