Longest Substring without Repeating Characters

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

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

Longest Substring Without Repeating Characters

Problem Statement

Given a string, find the length of the longest substring that does not have any repeating characters.

Examples

Sample Example 1

Input:

• string = "bbbbbb"

Output: length = 1

Sample Example 2

Input:

• string = "pwwkew"

Output: length = 3

Sample Example 3

Input:

• string = ""

Output: length = 0

Explanation: An empty string is passed as input, so there is no substring at all.

Solution

The idea is to use a sliding window, along with a map that remembers the last position where each character appeared.

Steps

• We keep two pointers: start (the left edge of our window) and end (the right edge, which moves forward one step at a time).
• We use a map called lastIndex. This stores the most recent index where each character was seen.
• As we move end forward through the string:
  • We check the current character. If we have seen it before, and that earlier position is inside our current window (at or after start), we move start to just after that earlier position. This removes the repeated character from our window.
  • We update lastIndex with the character's new position.
  • We update our longest result if the current window (end - start + 1) is bigger than what we've found so far.
• At the end, longest holds the length of the longest substring with no repeating characters.

Code

function findLongestSubstring(str) {
    let start = 0;
    let lastIndex = new Map(); // char -> most recent index seen
    let longest = 0;

    for (let end = 0; end < str.length; end++) {
        const curr = str[end];

        if (lastIndex.has(curr) && lastIndex.get(curr) >= start) {
            start = lastIndex.get(curr) + 1; // jump start past the previous occurrence
        }

        lastIndex.set(curr, end); // always update position
        longest = Math.max(longest, end - start + 1); // always update the max
    }

    return longest;
}