3. Longest Substring Without Repeating Characters

Problem Statement

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

Examples

Example 1:

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

Example 2:

Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.

Difficulty

Medium

Constraints

• 0 ≤ s.length ≤ 5 * 10⁴
• s consists of English letters, digits, symbols and spaces.

Solution 1: Sliding Window (Using Two pointers + Hash Table)

Approach:

1. Initialize an empty Set to store characters of the current window.
2. Use two pointers i and j to represent the window. j is the leading pointer, and i is the trailing pointer.
3. Iterate through the string with j. If the character s[j] is already in the set, it means we have a duplicate.
4. Continuously remove s[i] from the set and increment i until s[j] is no longer in the set.
5. Add s[j] to the set and update the maximum length ans = max(ans, j - i + 1).

Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set st = new HashSet<>();
        int ans = 0;
        for (int i = 0, j = 0; j < s.length(); ++j) {
            char c = s.charAt(j);
            while (st.contains(c)) {
                st.remove(s.charAt(i++));
            }
            st.add(c);
            ans = Math.max(ans, j - i + 1);
        }
        return ans;
    }
}

C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set st;
        int ans = 0;
        for (int i = 0, j = 0; j < s.size(); ++j) {
            while (st.count(s[j])) {
                st.erase(s[i++]);
            }
            st.insert(s[j]);
            ans = max(ans, j - i + 1);
        }
        return ans;
    }
};

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        st = set()
        i = ans = 0
        for j, c in enumerate(s):
            while c in st:
                st.remove(s[i])
                i += 1
            st.add(c)
            ans = max(ans, j - i + 1)
        return ans

Complexity

Time: O(n) where n is the length of the string.

Space: O(k) where k is the number of unique characters in the string.

← All Problems