Longest Substring Without Repeating Characters

Problem description:

Given a string,¬†find the length of the longest substring without repeating characters, for example, s = “abcabc”, the longest substring without repeating characters is “abc” so the length is 3.

First Approach:

Like always, there is a non optimal solution, actually a quadratic solution, just loop the array and for each element loop the array again by keeping track of the elements that we have visited and stop when you find a repeating character, this will give us the longest substring without repeating characters. This solutions works but is too slow, can we do it better? yes.

A better approach:

We just need to look at it a little bit closer to realize that at each time we find a repeating character we don’t need to start again at position i + 1, because we know that all the remaining elements except the element at position i are unique. Let’s clarify this idea with an example:

s = “abcab”

1.- Lets start looping through our array, at first we have “a”, do we have already an “a”?, No. So let’s store “a” and continue with the next element.

2.- Now we have “b”, do we have already a “b” ?, Nope, so we store the “b” and continue.

3.- We get a “c” , we don’t have any “c” already stored, so store it and continue.

4.- Now we get an “a”, do we have already an “a”?, Yes we have. So now we know that so far all the elements are different but the “a” at position 0 and the “a” at position 3, with our first approach we just would start again at position 1, but it’s not necessary because we know that all the remaining elements from index 1 to 3 are different, so we just ignore the “a” at position 0 and continue with the next character. By doing this we are gonna avoid a bunch of operations and now we have a much more efficient algorithm.

Here the working code in Java:


public int lengthOfLongestSubstring(String s) {

    int max = 0;
    int count = 0;
    int a[] = new int[26];
    Arrays.fill(a, -1);

    for(int i = 0; i < s.length(); ++i)
    {

        if(a[s.charAt(i) - 'a'] >= 0) {
            int from = a[s.charAt(i) - 'a'];
            count = i - a[s.charAt(i) - 'a'];
            a = new int[26];
            Arrays.fill(a, -1);

            for(int j = from + 1; j <= i; ++j)
                a[s.charAt(j) - 'a'] = j;
        }
        else {
            count++;
            a[s.charAt(i) - 'a'] = i;
        }

        max = Math.max(max, count);
    }

    return max;
 }

Advertisements