Longest Substring Without Repeating Characters

Previous
Next

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

Problem

We need to find Longest Substring Without Repeating Characters

Solution

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

Output:

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.

Previous
Next

Join Our News Letter – Stay Updated

Subscribe to Awesome Java Content.




Add Comment

Join Our News Letter - Stay Updated

Subscribe to Awesome Java Content.
You can like our facebook page Java2blog