Coder's Cat

## LeetCode: Longest Substring Without Repeating Characters

2019-10-17

LeetCode longest substring without repeating characters : explanations and solutions with Cpp/Java/Python

## Explanation

### Naive solutions

According to problem description, the first solution should be enumerating all the ranges of the string, check whether characters in range[i, j] are unique, if it’s true, we compute the distance and compare it with the current distance, choose the max one as answer.

But how to check whether a sub-string is constructed with all unique characters? HashSet is need here, so the pseudo code is:

It’s easy to figure out, there are three loop range in pseudo code.

Time complexity: $O(N^3)$ Space complexity: We most need $O(K)$ space, where K is the number of different characters, 26 is enough for letters.

### Optimization: reduce the double check with hashmap

Notice in the naive solution, we have a gap double checked in range. For example, we checked range[1, 4) in first loop, we also checked range [2, 4) in later loop, that’s what we can optimize on time complexity.

Actually we can maintain a window slice, tracking all unique characters in the windows, if next character can be found in the previous window, which means we need to update the window to current position. How can we quickly found out whether a character occurs in window? A hashset or hashmap can be used here.

Here we come out the C++ version:

Take a example input ‘abccde’, it’s output should be:

The time complexity is: $O(N)$, and space complexity is same as naive solution.

An alternative implementation is use hashmap to store the index of characters, which can be fetched to check the distance of range:

### Other optimization

If characters have fixed range, we just use a table replace the hashmap, using table will also perform better, and more suitable for C programming languages which don’t have hashmap in standard library.

## Java

Java is same with C++ version:

## Python

Preparing for an interview? Checkout this!