string - Find longest substring without repeating characters

Question

Given a string S of length N find longest substring without repeating characters.

Example:

Input: "stackoverflow"

Output: "stackoverfl"

If there are two such candidates, return first from left. I need linear time and constant space algorithm.

Answer 1

1. You are going to need a start and an end locator(/pointer) for the string and an array where you store information for each character: did it occour at least once?

2. Start at the beginning of the string, both locators point to the start of the string.

3. Move the end locator to the right till you find a repetition (or reach the end of the string). For each processed character, store it in the array. When stopped store the position if this is the largest substring. Also remember the repeated character.

4. Now do the same thing with the start locator, when processing each character, remove its flags from the array. Move the locator till you find the earlier occurrence of the repeated character.

5. Go back to step 3 if you haven't reached the end of string.

Overall: O(N)