3. Longest Substring Without Repeating Characters Solved

[Lomanu4]

Given a string s, find the length of the longest substring without duplicate 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.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.

Core Idea (Sliding Window with Two Pointers)

• We want to find a window in the string that doesn't contain any repeating characters.
• We use two pointers, left and right, to define this window.
• A set (char_set) keeps track of the unique characters in the current window.
• If we find a duplicate, we shrink the window from the left until the duplicate is removed.

def length_of_longest_substring(s: str) -> int:
char_set = set()
left = 0
max_length = 0

for right in range(len(s)):
while s

in char_set:
char_set.remove(s

)
left += 1
char_set.add(s

)
max_length = max(max_length, right - left + 1)

return max_length

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.

Why It’s Efficient:

• Each character is added and removed at most once → O(n)
• Set gives constant time lookup → fast

When to Use This Technique:

• Use this sliding window + set pattern whenever:
• You need the longest substring/subarray with no repeats
• You need to maintain a dynamic window of valid elements

Time & Space Complexity:
Type Value
Time O(n) (each character is visited at most twice)
Space O(min(n, m)) where m is the character set size (e.g. 26 lowercase)

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.