Longest Substring Without Repeating Characters

11 Dec 2011

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Ok, so a brute-force solution takes O(n^3), though we can improve it to O(n^2).

The O(n^2) solution comes from the observation that:

a[i] is the starting point and a[i..j] has no repeating characters but a[i..j+1] has repeating characters.

We can just stop and move the starting point to a[i+1].

Now we need more observations.

Observation 1

We don't need to rescan. Let's say:

a[i] is the starting point, a[i..j] is valid but a[i..j+1] is invalid.

We can move the starting point to a[i+1] and iterates from a[j] instead.

This is because a[i+1..j] is guaranteed to have no repeating characters as a[i..j] has no repeating characters.

Well, this observation obviously leads to an O(n) solution, which utilizes 2 pointers. I'll leave it to future Tanin in order to devise a complete solution.

Detecting repeating characters

Now, how do we detect repeating characters? Using a hash is a good one if the given string is guaranteed to have only a-z.

Let's take a look at Leetcode.com.

Well, yup, they assume that the string contains only a-z.

Hurray! I have solved this one by myself.