Algorithm Puzzles ~~everyday~~ ~~every week~~ sometimes: Longest Substring Without Repeating Characters

## Puzzle

Puzzle from leetcode:

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

Example 1:

Input: “abcabcbb”

Output: 3

Explanation: The answer is “abc”, with the length of 3.

Example 2:

Input: “bbbbb”

Output: 1

Explanation: The answer is “b”, with the length of 1.

Example 3:

Input: “pwwkew”

Output: 3

Explanation: The answer is “wke”, with the length of 3.

Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

## Solving

### First came out solution

Traverse substring(not all of them, with a little bit optimization)

1 | class Solution { |

Time complexity: O(n^3)

But this solution is not good enough since the time complexity is O(n^3). Only better than 62.78% cpp users.

### Sliding Window

Checked the reference answer, there is another solution: using sliding Window.

1 | class Solution { |

Time complexity: O(n)

It’s better than 85.71% now.

### Assuming ASCII 128

The third way to solve this is assuming the string inputs are all ASCII 128 characters… In this case no hash table is needed.

1 | class Solution { |

This solution is faster than 95.65%.