Longest Substring Without Repeating Characters

13 May 2026 0 Likes

Problem Description

Given a string s, find the length of the longest substring without repeating characters. A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The longest substring without repeating characters is: "abc". Its length is: 3
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The substring: "b" is the longest substring without repeating characters.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The longest substring without repeating characters is: "wke". Its length is: 3

Note that: "pwke" is not a valid substring because the characters are not contiguous.

Constraints

1. The string may contain English letters, digits, symbols, and spaces. Its length may vary depending on platform constraints.
2. The output should represent the length of the longest substring that contains only unique characters.
3. Efficient solutions are expected to process the string in linear time.

Understanding the Problem

The problem asks us to find the longest contiguous substring in which every character appears only once. For example, in the string "abcabcbb", we can form substrings like "a", "ab", and "abc", where all characters are unique.

However, when the next character 'a' appears again, the substring "abca" contains a duplicate character and becomes invalid. At that point, we must adjust the current substring while continuing the search efficiently.

The main challenge is to avoid repeatedly rescanning characters whenever a duplicate appears, so efficient solutions dynamically maintain a valid window of unique characters while traversing the string.

Hints

The first hint is to think about maintaining a moving window of unique characters instead of checking every possible substring separately. A sliding window technique works very well here because the substring is always contiguous.

Whenever a duplicate character appears, move the left side of the window forward until the duplicate is removed.

A HashSet or HashMap can help efficiently track characters currently present inside the window. While expanding and shrinking the window, continuously update the maximum substring length found so far.

Solutions

OPTIMAL

Sliding Window Unique Character Tracking Solution

This approach uses the sliding window technique to efficiently maintain a substring containing only unique characters. Instead of checking every possible substring separately, we dynamically expand and shrink a valid window while traversing the string.

Two pointers are maintained:

i → starting index of the current window
j → ending index of the current window

A HashSet is used to track characters currently present inside the window. As the right pointer expands, every new character is checked:

1. If the character is not already present in the set, it is added to the window and the current substring remains valid.
2. If a duplicate character appears, we continuously move the left pointer forward while removing characters from the set until the duplicate is removed.

At every step, the current valid substring length is calculated using: j - i + 1 and the maximum length found so far is updated.

For example, in: "abcabcbb", the window initially grows as: "a" → "ab" → "abc". When another 'a' appears, the window shrinks from the left until the duplicate is removed, after which expansion continues again.
public class A_SlidingWindow {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n < 1) {
            return n;
        }
        Set<Character> set = new HashSet<>();
        int maxLength = 0;
        int i = 0;
        int j = 0;

        while (j < n) {
            char c = s.charAt(j);
            while (set.contains(c)) {
                set.remove(s.charAt(i));
                i++;
            }
            set.add(c);
            maxLength = Math.max(maxLength, j - i + 1);
            j++;
        }
        return maxLength;
    }
}

class Solution:
    def lengthOfLongestSubstring(self, s):
        n = len(s)

        if n < 1:
            return n

        seen = set()
        max_length = 0
        i = 0
        j = 0

        while j < n:
            c = s[j]

            while c in seen:
                seen.remove(s[i])
                i += 1

            seen.add(c)
            max_length = max(max_length, j - i + 1)

            j += 1

        return max_length
Time Complexity
O(n)
Space Complexity
O(1)

(Because the character set size is bounded)

Conclusion

The Longest Substring Without Repeating Characters problem is one of the most important interview problems for understanding the sliding window technique. The problem demonstrates how dynamic window adjustment can efficiently maintain valid conditions while traversing a string.

Mastering this problem helps build a strong understanding of window-based traversal, hash-based lookup, and efficient substring processing, which are commonly used in coding interviews and real-world applications.

💬 Comments