[leetcode] Longest Substring Without Repeating Characters | 最长的unique char组成的substring

Posted by: lexigrey on: November 2, 2013

• In: leetcode
• Leave a Comment

这题完全没印象，后来发现是之前做用了string.indexOf这个函数cheat成功了。这也是two pointers一快一慢的练习题，挺难做的，需要重做。

• i：当前unique substring的头
• j：当前unique substring的尾
• 注意最后可能忘记算最后一段的长度了（因为dup那个条件已经不存在）

public int lengthOfLongestSubstring(String s) {
    int i = 0, len = 0, n = s.length();
    char A[] = s.toCharArray();
    Set<Character> set = new HashSet<Character>();
    for (int j = 0; j < n; j++) {
        if (set.contains(A[j])) { //found dup
            len = Math.max(len, j - i);
            while (i < n && A[i] != A[j]) {
                set.remove(A[i]);
                i++;
            }
            i++;
        } else {
            set.add(A[j]);
        }
    }
    return Math.max(len, n - i);
}

Tags: array, redo, 一快一慢双指针