mediumStringsSliding WindowHash MapSliding Window

Longest Substring Without Repeating Characters

Est. Time: 25 minTime: O(n)Space: O(min(n, m))

Description

Given a string s, find the length of the longest substring without repeating characters.

Examples

Example 1 Input:s = "abcabcbb"

Output:3

Explanation: The answer is "abc", with length 3.

Example 2 Input:s = "bbbbb"

Output:1

Explanation: All chars are "b", so longest is 1.

Example 3 Input:s = "pwwkew"

Output:3

Explanation: The answer is "wke", with length 3.

Constraints

▪0 <= s.length <= 5 * 10^4
▪s consists of English letters, digits, symbols, and spaces.

Hints

Hint 1Show

Use a sliding window approach.

Hint 2Show

Maintain a set of characters in the current window.

Hint 3Show

When a duplicate is found, shrink the window from the left.

Starter Code

Solution.cpp

1class Solution {
2public:
3    int lengthOfLongestSubstring(std::string s) {
4        // Your code here
5        return 0;
6    }
7};

Solution

Solve the problem first before reviewing the solution!

Up Next

Valid Parentheses

Back to C++ Problems

mediumStringsSliding WindowHash MapSliding Window

Longest Substring Without Repeating Characters

Est. Time: 25 minTime: O(n)Space: O(min(n, m))

Description

Given a string s, find the length of the longest substring without repeating characters.

Examples

Example 1 Input:s = "abcabcbb"

Output:3

Explanation: The answer is "abc", with length 3.

Example 2 Input:s = "bbbbb"

Output:1

Explanation: All chars are "b", so longest is 1.

Example 3 Input:s = "pwwkew"

Output:3

Explanation: The answer is "wke", with length 3.

Constraints

▪0 <= s.length <= 5 * 10^4
▪s consists of English letters, digits, symbols, and spaces.

Hints

Hint 1Show

Use a sliding window approach.

Hint 2Show

Maintain a set of characters in the current window.

Hint 3Show

When a duplicate is found, shrink the window from the left.

Starter Code

Solution.cpp

1class Solution {
2public:
3    int lengthOfLongestSubstring(std::string s) {
4        // Your code here
5        return 0;
6    }
7};

Solution

Solve the problem first before reviewing the solution!

Up Next