Longest Substring Without Repeating Characters — Medium Coding Problem | Setups Works Lab

Longest Substring Without Repeating CharactersMedium

Longest Substring Without Repeating Characters

Name: Setups Works Lab
Brand: Setups Works Lab
Availability: InStock

MediumSliding Window

Problem Statement

Given a string S, find the length of the longest substring that contains no duplicate characters.

Input (stdin)

1 ≤ |S| ≤ 10^5
S consists of ASCII printable characters.

Output (stdout)

where L is the maximum length of a substring of S with all distinct characters.

Example

Input

abcaefgh

Output

Explanation The substring "bcaefg" (or "caefgh") has length 6 and contains no repeating characters.

Example 1

Input: abcaefgh

Output: 6

Longest distinct substring is "bcaefg" or "caefgh".

Example 2

Input: bbbb

Output: 1

Only one character can be taken because all are the same.

Constraints

Time limit: 1 second
Memory limit: 256 MB
Expected time complexity: O(|S|)

Hints

stringsliding-windowhashmap

Run your code to see test results here.