leetcode: Longest Substring Without Repeating Characters

Problem Description:

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.

Solution and Precautions:

An O(N^2) solution is not hard to come up with, that is, start from each single character say s[i] in the given string, try to find the longest substring without reapeting charaters starting from s[i], when encountering any repeated character, stop, the the length of this substring is the longest substring starting from s[i] without repeating characters, we then start from s[i+1] to do the same check again and so on. Each check cost O(N) time while there could be N such checks and thus the time complexity is O(N^2).

However, if one thinks about it further, suppose start from s[i] and at s[j] (j > i) we found s[j] a repeated character. And we will start from s[i+1] to do the same scanning again. This is absolutely unnecessary. We can claim that, the whole range [i, j] does not need to be scanned anymore, suppose the repeated character with s[j] in the range [i, j-1] is at position x (x >= i and x < j), obviously any substring starting from any character in [i, x] will get a shorter sub string since we will encouter s[j] later on anyways, so the next start point actually should be s[x+1], and also remember we don’t need to scan s[x+1] to s[j] anymore and could start from s[j+1] to do the check. As a result, both i and j will scan through the whole string exactly once, and give a O(N + N) = O(N) linear time complexity.

Written on May 6, 2013