**I just announced the new *** Learn Spring * course, focused on the fundamentals of Spring 5 and Spring Boot 2:

*Learn Spring*course, focused on the fundamentals of Spring 5 and Spring Boot 2:

Last modified: December 8, 2018

]

In this tutorial, compare ways to find the longest substring of unique letters using Java. For example, the longest substring of unique letters in “CODINGISAWESOME” is “NGISAWE”.

Let’s start with a naive approach. To begin with, **we can examine each substring whether it contains unique characters:**

String getUniqueCharacterSubstringBruteForce(String input) { String output = ""; for (int start = 0; start < input.length(); start++) { Set<Character> 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).**

Now, let’s take a look at an optimized approach. We start traversing the string from left to right and maintain track of:

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

String getUniqueCharacterSubstring(String input) { Map<Character, Integer> 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; }

For every new character, we look for it in the already visited characters. If the character has already been visited and is part of the current substring with non-repeating characters, we update the start index. Otherwise, we’ll continue traversing the string.

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

**This approach is also known as the sliding window pattern.**

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")); }

Here, we try and **test boundary conditions as well as the more typical use cases**.

In this tutorial, we’ve learned how to use the sliding window technique to find the longest substring with non-repeating characters.

And, as always, the source code is available over on GitHub.

]