Longest Substring Without Repeating Characters

Find the length of the longest substring without repeating characters using the sliding window technique with a hash set to track unique characters.

Sliding Window Hash Set LC 3 Medium

Problem Statement

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

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.

Example 3:

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

Interactive Visualization

Input String:

Presets:

Speed: 1000ms

Current Window Length

Max Length Found

Best Substring Found

—

Hash Set (Current Window Characters)

Empty

Code

fun lengthOfLongestSubstring(s: String): Int {    val charSet = mutableSetOf<Char>()    var left = 0    var maxLen = 0        for (right in s.indices) {        while (s[right] in charSet) {            charSet.remove(s[left])            left++        }        charSet.add(s[right])        maxLen = maxOf(maxLen, right - left + 1)    }    return maxLen}

def lengthOfLongestSubstring(s):    char_set = set()    left = 0    max_len = 0        for right in range(len(s)):        while s[right] in char_set:            char_set.remove(s[left])            left += 1        char_set.add(s[right])        max_len = max(max_len, right - left + 1)        return max_len

Ready to start

How It Works

Key Insight

The sliding window technique maintains a variable-size window of unique characters. We use a hash set to efficiently check for duplicates in O(1) time. When we encounter a duplicate character, we shrink the window from the left until the duplicate is removed.

Algorithm Steps

Initialize: Create an empty hash set, set left = 0, and max_len = 0
Expand Window: For each position right from 0 to len(s) - 1
Remove Duplicates: While s[right] is in the set, remove s[left] and increment left
Add Character: Add s[right] to the set
Update Maximum: Update max_len with the current window size (right - left + 1)
Return: After processing all characters, return max_len

Complexity Analysis

Time Complexity:	O(n)	Each character is visited at most twice (once by right, once by left)
Space Complexity:	O(min(n, m))	where n is string length and m is the character set size (at most 128 ASCII or 256 extended ASCII)