Solution: Longest Substring without Repeating Characters

Explore how to efficiently solve the problem of finding the longest substring without repeating characters. This lesson teaches you to implement a sliding window approach combined with a hash map to track characters and their indexes, optimizing the solution for linear time and constant space complexity. You'll learn to handle repeating characters dynamically by adjusting the window's start position, enabling you to solve similar string manipulation problems with ease.

We'll cover the following...

Statement
Solution
- Naive approach
- Optimized approach using sliding window

Statement

Given a string, str, return the length of the longest substring without repeating characters.

Constraints:

$1$ $\leq$ str.length $\leq$ $10^5$
str consists of English letters, digits, symbols, and spaces.

Solution

So far, you’ve probably brainstormed some approaches on how to solve this problem. Let’s explore some of these approaches and figure out which one to follow while considering time complexity and any implementation constraints.

Naive approach

The naive approach is to explore all possible substrings. For each substring, we check whether any character in it is repeated. After checking all the possible substrings, the substring with the longest length that satisfies the specified condition is returned.

The total time complexity of this solution is $O(n^3)$ ...