Home Computer Science Java Algorithm

[384 · Longest Substring Without Repeating Characters - LintCode](https://www.lintcode.com/problem/384/

# Description

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

# Example

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The longest substring is "abc".

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The longest substring is "b".

# Challenge

time complexity O(n)

# Solution

當走到 i 時，只要發現和 set 裡的字符相等，用另一指針找到之前出現過 & 重覆的字符，把它刪走，指針向右移。然後重新再加上現在 i 的這位字符。

# Code

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        Set<Character> set = new HashSet<>();
        int max = 0;
        int j = 0;
        for (int i = 0; i < s.length(); i++) {
            if (set.contains(s.charAt(i))) {
            // 同向雙指針 都是 for + while <--- while: 不滿足則循環到滿足搭配為止
                while (j < i && set.contains(s.charAt(i))) { // 把一開始的第一個 a 刪走，再把現任的 a 加上；
                // 一直刪，直到刪到 j 與當前 charAt (i) 一樣為止
                    set.remove(s.charAt(j));
                    System.out.println("第"+ i + "次 remove了: "+ s.charAt(j) + "  ;j = " + j );
                    j++;
                }
                set.add(s.charAt(i));
                  System.out.println("第"+ i + "次 add了: "+ s.charAt(i) );
            } else {
                set.add(s.charAt(i));
            }
            max = Math.max(max, set.size());
        }
        return max;
    }
}
input
abcabcbb

output
結果：
3

第3次 remove了: a  ;j = 0
第3次 add了: a
第4次 remove了: b  ;j = 1
第4次 add了: b
第5次 remove了: c  ;j = 2
第5次 add了: c
第6次 remove了: a  ;j = 3
第6次 remove了: b  ;j = 4
第6次 add了: b
第7次 remove了: c  ;j = 5
第7次 remove了: b  ;j = 6
第7次 add了: b