[LeetCode][3. Longest Substring Without Repeating Characters] Two Pointers: Sliding Window with HashSet

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 924 阅读时长 ≈ 1 分钟

By Long Luo

This article is the solution Two Pointers: Sliding Window with HashSet of Problem 3. Longest Substring Without Repeating Characters.

Intuition

We can just simulate the process.

Using a Sliding Window from left to right of the string, and a HashSet to make every character is unique in the sliding window.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() <= 1) {
        return s.length();
    }

    int ans = 0;
    int len = s.length();
    Set<Character> set = new HashSet<>();
    int left = 0;
    int right = 0;
    while (right < len) {
        while (right < len && !set.contains(s.charAt(right))) {
            set.add(s.charAt(right));
            right++;
        }

        ans = Math.max(ans, right - left);
        set.remove(s.charAt(left));
        left++;
    }

    return ans;
}

Analysis

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(128)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗