Longest substring with unique characters Find the length of the longest substring without repeating characters


Any comments on my code?

public class LongestSubstring {
    /**
     * First version. O(n^2) runtime
     * For each character, find the longest substring starting
     * with this character and update max
     * @param s
     * @return
     */
    public int lengthOfLongestSubstringV1(String s) {
        char[] c = s.toCharArray();
        int n = c.length;
        int max = 0;

        for (int i = 0; i &lt; n; i++){
            // localMax is the size of the longest substring starting with character i
            // and that has no repeated character
            int localMax = findLocalMax(c,i);
            // update max if localMax &gt; max
            max = (max &gt; localMax) ? max : localMax;
        }
        return max;
    }

    /**
     * find the largest substring that has no repeated character
     * starting at character i in array c
     * @param c
     * @param i
     * @return
     */
    public int findLocalMax(char[] c, int i){
        int n = c.length;
        // seen: characters already seen
        HashSet&lt;Character&gt; seen = new HashSet&lt;Character&gt;();
        int localMax = 0;

        for (int j = i; j &lt; n; j++){
            // c[j] was seen already
            if (seen.contains(c[j])){
                return localMax;
            }
            else{
                seen.add(c[j]);
                localMax++;
            }
        }
        return localMax;
    }

    /**
     * Second version. O(n^2) runtime
     * if a character is seen again,
     * @param s
     * @return
     */
    public int lengthOfLongestSubstringV2(String s) {
        char[] c = s.toCharArray();
        int n = c.length;
        // currentLetters: HashSet of the letters contained in the current substring
        HashSet&lt;Character&gt; currentLetters = new HashSet&lt;Character&gt;();
        // pointer1 points to the beginning of the substring
        int pointer1 = 0;
        int max = 0;
        int currentCount = 0;

        // pointer2 points to the end of the substring
        for (int pointer2 = 0; pointer2 &lt; n; pointer2++){
            if (currentLetters.contains(c[pointer2])){
                // if the letter c[pointer2] has already been seen
                // remove all the letters before the first occurrence
                // of this letter to consider the substring beginning after
                // this first occurrence
                while (c[pointer1] != c[pointer2]){
                    currentCount--;
                    currentLetters.remove(c[pointer1]);
                    pointer1++;
                }
            }
            else{
                // otherwise, add the letter to the substring
                currentCount++;
                currentLetters.add(c[pointer2]);
            }
            max = (max &gt; currentCount) ? max : currentCount;
        }

        return max;
    }
}

public class TestLongestSubstring {
    LongestSubstring lgs = new LongestSubstring();
    @Test
    public void testEmptyString(){
        String s = "";
        assertEquals(0,lgs.lengthOfLongestSubstringV1(s));
        assertEquals(0,lgs.lengthOfLongestSubstringV2(s));
    }

    @Test
    public void testSameCharacterExpects1(){
        String s = "bbbb";
        assertEquals(1,lgs.lengthOfLongestSubstringV1(s));
        assertEquals(1,lgs.lengthOfLongestSubstringV2(s));
    }

    @Test
    public void testabcabcbbExpects3(){
        String s = "abcabcbb";
        assertEquals(3,lgs.lengthOfLongestSubstringV1(s));
        assertEquals(3,lgs.lengthOfLongestSubstringV2(s));
    }
}


public class TestLongestSubstringRunner {
    public static void main(String args[]){
        Result result = JUnitCore.runClasses(TestLongestSubstring.class);
        for (Failure failure : result.getFailures()){
            System.out.println(failure.toString());
        }
        System.out.println(result.wasSuccessful());
    }
}
Time complexity

The time complexity is not \$O(N^2)\$ as you estimated, but actually \$O(N M)\$, where n is the length of the input string and m is the number of unique characters in the input string. This makes a big difference, because in practice m is typically bounded by a constant, the size of the alphabet, which in the case of ascii is 256. If m is a constant then the asymptotic complexity becomes simply \$O(N)\$, which is great news for you.

Optimizations

A small tweak can make the implementation significantly faster: change the loop condition in the outer function to go until n - max instead of n.

If you know the size of the alphabet in advance, then you can use a boolean[] instead of a set, with the character codes as indexes. It's simpler, and by reducing the autoboxing, faster too.

Use interface types instead of implementations

You could declare the HashSet as a Set instead.