Longest Substring Without Repeating Characters

0
770

Longest Substring Without Repeating Characters

In this tutorial, you’ll learn how to use Java to compare various methods for finding the longest substring without repeating characters. For instance, in the word “CODINGISAWESOME,” the longest substring without repeating characters is “NGISAWE.”

Brute Force Approach

Let’s begin with a simplistic approach. To begin, we can look at each substring to see if it has any unique characters.

String getUniqueCharacterSubstringBruteForce(String input) {
String output = “”;
for (int start = 0; start < input.length(); start++) { Set visited = new HashSet<>();
int end = start;
for (; end < input.length(); end++) {
char currChar = input.charAt(end);
if (visited.contains(currChar)) {
break;
} else {
visited.add(currChar);
}
}
if (output.length() < end – start + 1) {
output = input.substring(start, end);
}
}
return output;
}

Since there are n*(n+1)/2 possible substrings, the time complexity of this approach is O(n^2).

Optimized Approach

Let’s take a look at a more effective process. We begin by traversing the string from left to right, keeping track of our progress.

  • a lookup table of already visited characters
  • the current substring with non-repeating characters with the help of a start and end index
  • the longest non-repeating substring output

String getUniqueCharacterSubstring(String input) {
Map visited = new HashMap<>();
String output = “”;
for (int start = 0, end = 0; end < input.length(); end++) {
char currChar = input.charAt(end);
if (visited.containsKey(currChar)) {
start = Math.max(visited.get(currChar)+1, start);
}
if (output.length() < end – start + 1) {
output = input.substring(start, end + 1);
}
visited.put(currChar, end);
}
return output;
}

We search for new characters in the characters we’ve already seen. We change the start index if the character has already been visited and is part of the current substring with non-repeating characters. Otherwise, we’ll keep going through the string.

Since we are traversing the string only once, the time complexity will be linear, or O(n).

Testing

Finally, let’s test thoroughly our implementation to make sure it works

@Test
void givenString_whenGetUniqueCharacterSubstringCalled_thenResultFoundAsExpected() {
assertEquals(“”, getUniqueCharacterSubstring(“”));
assertEquals(“A”, getUniqueCharacterSubstring(“A”));
assertEquals(“ABCDEF”, getUniqueCharacterSubstring(“AABCDEF”));
assertEquals(“ABCDEF”, getUniqueCharacterSubstring(“ABCDEFF”));
assertEquals(“NGISAWE”, getUniqueCharacterSubstring(“CODINGISAWESOME”));
assertEquals(“be coding”, getUniqueCharacterSubstring(“always be coding”));
}

We try to test boundary conditions as well as more common use cases here.

Conclusion

We learned how to find the longest substring with non-repeating characters by using the sliding window technique in this tutorial.

LEAVE A REPLY

Please enter your comment!
Please enter your name here