Longest substring without repeating characters
DSA, Medium
Which structure or algorithm, and what does it cost.
You get a string s. A substring is a run of consecutive characters. Return the length of the longest substring in which no character appears twice. Return 0 for an empty string.
Examples
Input "abcabcbb"
Output 3
Why for
"abc".Input "bbbbb"
Output 1
Why because every character repeats.
Input "abba"
Output 2
Why for
"ab" or "ba". The second a must not pull the window start back to before the second b.Constraints
- 0 <= length of
s<= 100,000. sholds any printable ASCII characters (at most 128 kinds).
Your answer must contain
- A simple method and its cost; the better method and why it is correct; code; time and memory; a hand trace of example 3.