Longest Substring without Repeating Characters

Try to solve the Longest Substring without Repeating Characters problem.

We'll cover the following

Statement#

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

Constraints:

  • 11 ≤\leq input_str.length ≤1000\leq 1000
  • input_str consists of English letters, digits, and spaces.

Examples#

Created with Fabric.js 3.6.6 string b b b b b b length = 1 Input Output Sample example 1

1 of 3

Created with Fabric.js 3.6.6 string p w w k e w Output length = 3 Input Sample example 2

2 of 3

Created with Fabric.js 3.6.6 Output string "" Empty string passed as an input length = 0 Input Sample example 3

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps us to check if you’re solving the correct problem:

Longest Substring Without Repeating Characters

1

What should be the output if the following string is given as an input?

str = “conceptoftheday”

A)

8

B)

6

C)

5

D)

13

Question 1 of 40 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Initialize an empty hash map and a variable to track character indexes and the start of the window, respectively.

Traverse the string character by character. For each character, if the hash map does not contain the current character, store it with its index as the value.

If the hash map contains the current character and its index falls within the current window, a repeating character is found. Otherwise, store it in the hash map with its index as the value.

When a repeating character is found, update the start of window to the previous location of the current element and increment it. Also, calculate the length of the current window.

Update the longest substring seen so far if the length of the current window is greater than its current value.

Return the length of the longest substring.

Try it yourself#

Implement your solution in the following coding playground:

Python
usercode > main.py
Input #1
Longest Substring without Repeating Characters

Solution: Best Time to Buy and Sell Stock

Solution: Longest Substring without Repeating Characters