SLDW0103 - Editorial

Problem Link - Longest Substring Without Repeating Characters

Problem Statement

Given a string S of length N, output the length of the longest substring of S with non-repeating characters. This means no character in the substring should appear more than once. We can use the sliding window technique to solve this problem.

To implement this, we’ll use a frequency map to track the occurrences of characters. We’ll expand the window by adding characters until a duplicate is found. When a duplicate character is encountered, we’ll start shrinking the window from the left until each character in the window appears only once.

Approach

The code uses a sliding window with two pointers, left and right, to find the longest substring without repeating characters. Moving right over each character, we track character counts in a frequency map. When a duplicate is found (frequency > 1), left is moved forward to shrink the window until all characters are unique. After each adjustment, the window length is calculated, updating longest if this length is the largest so far. This continues until all characters are scanned, with longest holding the maximum length of a substring without repeats.

Time Complexity

O(N), where N is the length of the string, as each character is processed at most twice.

Space Complexity

O(K), where K is the number of unique characters, due to the frequency map used to store character counts.