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 max
max = (max > 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 seen = new HashSet();
int localMax = 0;

for (int j = i; j currentLetters = new HashSet();
// 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 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

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.

StackExchange Code Review Q#91230, answer score: 6