Grokking Data Structures & Algorithms for Coding Interviews

0% completed

​

Solution: Longest Substring Without Repeating Characters (medium)

Problem Statement

Given a string, identify the length of its longest segment that contains distinct characters. In other words, find the maximum length of a substring that has no repeating characters.

Examples:

  1. Example 1:

    • Input: "abcdaef"
    • Expected Output: 6
    • Justification: The longest segment with distinct characters is "bcdaef", which has a length of 6.

  2. Example 2:

    • Input: "aaaaa"
    • Expected Output: 1
    • Justification: The entire string consists of the same character

.....

.....

.....

Like the course? Get enrolled and start learning!
L

lestatcheb

· 2 years ago

Looks like the provided solution is not perfect, when we found a duplicate char - we should jump the left pointer to the prev duplicate char position + 1 instead of just doing start += 1

class Solution2:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # key: char
        # value: index of char in s
        m = {}
        max_length = 0  # init to 0, to handle empty string cases
        left = 0
        for right in range(len(s)):
            c = s[right]

            # if found a duplicate, and it's in the current window,
            # move left to the next non-duplicate position
            if c in m and m[c] >= left:
                left = m[c] + 1
            m[c] = right

            cur_length = right - left + 1
            max_length = max(max_length, cur_
Show 1 reply
S

solomononaiwu

· a year ago

By using an hashset for the sliding window. It makes the sliding window pattern very easy to understand.