Longest Substring Without Repeating Characters


In this tutorial, we will see Find Longest Substring Without Repeating Characters in java.


We need to find Longest Substring Without Repeating Characters


Brute force solution

Find all the substring and check the Longest Substring Without Repeating Characters but time complexity will be O(n^3) in this case.

Linear time solution

We can solve this problem in linear time by using some extra spaces.

Here is simple algorithm for solving this problem:

  • Create a visited array and initialize it with -1. This array will track current index for the character.
  • Iterate over String and track the previousIndex. previousIndex is nothing but value of index in visited array
  • If current character is not yet repeated(previousIndex = -1) or it is not in current non repeating character String(i – currentLength > previousIndex) then just increase the current index.
  • If current character is present in current non repeating character String  then
    • Update the current length to start from the next character of previousIndex.
  • Update the index of current character in visited array.

Java program to find longest substring without repeating characters


The input string is TheJavaTutorial
Longest substring without repeating character: vaTutori

That’s all about finding Longest Substring Without Repeating Characters. You can find more java interview programs.


Add Comment