Java Program to find Longest Substring Without Repeating Characters

              It is a typical problem in Strings. As the name indicates this concept reads a substring that should not contain any repeated characters.

To solve this problem, let us use a “Sliding Window Approach”. This approach deals with a window slide around the data.

Logic:

• ·       A window is maintained.
• ·       It has two pointers to point the start and end of the window.
• ·       When the window slides, pointers may expand or contract.

Steps:

• ·       Import the built in packages import java.util.HashMap and import java.util.Scanner.
• ·       Create a public class with a constructor and main() function.
• ·       Inside the constructor, initialize the pointers for start and longest.
• ·       At first, assign the values as zero.
• ·       Using a HashMap, create an object.
• ·       A loop is created to check for non-repeatable sub string.
• ·       To expand the window: it tracks the characters in current window and add the current character to HashMap object.
• ·       It also moves the pointer to right.
• ·       To contract the window: it checks the uniqueness of character and keep the window characters unique.
• ·       The length of maximum characters in substring is noted.
• ·       The loop is repeated until the entire string.
• ·       ‘main()’ function reads the string from user. Call the constructor and print the length of longest substring.

Program:

import java.util.HashMap;

import java.util.Scanner;

public class longestUniqueSubstringEg {

    public static int longestUniqueSubstringEg(String s) {

        HashMap<Character, Integer> chIndexMap = new HashMap<>();

        int longer = 0;

        int start = 0;

        for (int index = 0; index < s.length(); index++) {

            char currentChar = s.charAt(index);

            if (chIndexMap.containsKey(currentChar) && chIndexMap.get(currentChar) >= start) {

                start = chIndexMap.get(currentChar) + 1;

            }

            chIndexMap.put(currentChar, index);

            longer = Math.max(longer, index - start + 1);

        }

        return longer;

    }

    public static void main(String[] args) {

        Scanner scanner1 = new Scanner(System.in);

        System.out.print("Enter the String:");

        String ipStr= scanner1.nextLine();

        int res = longestUniqueSubstringEg(ipStr);

        System.out.println("Here, is the length of the longest substring without any repetition: " + res);

    }

}

Output:

C:\raji\blog>javac longestUniqueSubstringEg.java

C:\raji\blog>java longestUniqueSubstringEg

Enter the String:abcdef

Here, is the length of the longest substring without any repetition: 6

Thus, the java program to find Longest Substring Without Repeating Characters is explained. Keep coding!!!