Longest Substring Without Repeating Characters

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

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:

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