LeetCode 3. Longest Substring Without Repeating Characters (Java)

tags: leetcode Java substring

Description

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

找出字串s中沒有重複最長的子字串(substring)的長度

Example

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

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Idea

• 使用移動窗格方式去找出最大子字串
• 每個迴圈窗格window都往右移一格，並且判斷窗格內是否有與新加入的字元重複，如有重複將左邊指標left往右刪除字元直到窗格內未有重複字元為止
  • HashSet不會加入重複字元或字串
• max_len會在移動窗格最後判斷目前合法的窗格長度是否大於原本的值

Code

這樣的寫法會使時間複雜度為

$O(n)$，會遍歷整個字串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null) return 0;
        
        HashSet<Character> window = new HashSet<Character>();
        int max_len = 0;
        int left = 0;
        int len = 0;
        char[] ss = s.toCharArray();
        for (int i = 0;i < s.length();i++){
            while(window.contains(ss[i])){ //判斷是否有重複字元
                window.remove(ss[left]);
                left++; //指標因刪除往右一格
                len--;
            }
            window.add(ss[i]);
            len++;
            if(max_len < len)
                max_len = len;
        }
        return max_len;
    }
}