Table of Contents
If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
import java.util.Arrays; //Java program to find longest substring without repeating characters public class LongestSubstringWithoutRepeatingCharactersMain { static final int NO_OF_CHARS = 256; static String longestUniqueSubstringWRepeatingCharacter(String str) { int len = str.length(); int currentlength = 1; // length of current substring int maximumLength = 1; // result int previousIndex=-1; // previous index int i; String longestSubString=""+str.charAt(0); int visited[] = new int[NO_OF_CHARS]; // Initialize visited array with -1 Arrays.fill(visited, -1); /* Mark first character as visited by storing the index of first character in visited array. */ visited[str.charAt(0)] = 0; /* Start from the second character */ for(i = 1; i < len; i++) { previousIndex = visited[str.charAt(i)]; /* * If current character is not seen yet or is not part of current * non repeating character string, simply increase the length of non repeating character string * */ if(previousIndex == -1 || i - currentlength > previousIndex) currentlength++; /* If the current character is present in currently considered non repeating character string, then update non repeating character string to start from the next character of previousIndex. */ else { /* Before updating non repeating character, check for maximum length*/ if(currentlength > maximumLength) { maximumLength = currentlength; int startIndex=i-currentlength; longestSubString=str.substring(startIndex,i); } currentlength = i - previousIndex; } // update the index of current character visited[str.charAt(i)] = i; } // check for maximum length if(currentlength > maximumLength) { maximumLength = currentlength; int startIndex=i-currentlength; longestSubString=str.substring(startIndex,i); } return longestSubString; } /* Driver program to test above function */ public static void main(String[] args) { String str = "TheJavaTutorial"; System.out.println("The input string is "+str); String longestUniqueSubsttr = longestUniqueSubstringWRepeatingCharacter(str); System.out.println("Longest substring without repeating character: "+longestUniqueSubsttr); } } |
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.
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
