Find length of longest substring without repeating characters in Java

Length of the longest substring without repeating characters in Java.


Given a string, find the length of the longest unique substring.

Lets understand what is the input and the expected output.

Algorithm 


Iterate the string and keep track of last visited index of each character of the String,
Each time you pick a character from string, check if the last visited index of the character is present in the visitedIndex map,

  • If Not present, it means this character is not yet visited, so adding it in substring will still make unique string, add it and increment our count.
  • If Yes, it is present, it means we found one instance of sequence which is unique and may be longest.
    • Initialize maxCount if the above sequence is the longest one. 
    • Also, initialize the startIndex of the next sequence which would start from lastIndex of the repeated character + 1.

Example: If string is "abcdecmnopqra" in this case, 
we will visit "abcde" and visitedIndex map would be {a=0, b=1, c=2, d=3, e=4}.
when we encounter next 'c', we need to stop as that is already visited, so next sequence would be from last visited index of c (c = 2) + 1. that is from d (dec and so on)


Find length of the longest substring without repeating characters in Java

package com.javabypatel.misc;

import java.util.HashMap;
import java.util.Map;

/*

Input = "abcdecmnopqra"
Output: "decmnopqra" (size = 10)

Input = "abcabcbb"
Output: "abc" (size = 3)

Input = "ABDEFGABEF"
Output: "ABDEFG" (size = 6)

Input = "bbbbb"
Output: "b" (size = 1)

Input = "pwwkew"
Output: "wke" (size = 3)

 */

public class LongestUniqueSubstring {

    public static void main(String[] args) {
        //String str = "abcdecmnopqra";
        //String str = "abcabcbb";
        String str = "ABDEFGABEF";
        //String str = "bbbbb";
        //String str = "pwwkew";
        System.out.println(findLengthOfLongestUniqueSubstring(str));
    }

    private static String findLengthOfLongestUniqueSubstring(String str) {

        Map<Character, Integer> map = new HashMap<>();

        //In case if you only want to return count.
        int maxUniqueSequenceCount = 0;
        int count = 0;

        //When we encounter a character already present in a map, we need to remove all the character from the map
        //right from the first character we included in the sequence till the first instance of the character and
        //our next count sequence will start from first instance(index) of character encountered.

        //eg: abcdecxyzmnoy
        //abcde is the first sequence and the pointer is at abcdec
        //                                                       ^
        //Now we need to start from d and remove the occurrences of abc like we haven't encountered this before
        //for the next counting sequence.
        //So instead of removing the old sequence, I am taking the startingIndex which will help us keep track
        // of starting index of the new sequence and if the element say a is encountered in next sequence,
        // our visited map will have an entry for a but we will ignore it as the index of last encountered
        // in map will be before our next startingIndex.
        int startingIndex = 0;

        //To keep track of starting and ending index of the longest unique substring
        int maxStartIndex = 0;
        int maxEndIndex = 0;

        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);

            if (map.get(ch) != null && map.get(ch) >= startingIndex) {
                startingIndex = map.get(ch) + 1;
                count = (i - startingIndex) + 1;
                //+1 is for current character which is included at the end and removed from front;
            } else {
                count++;
            }

            //update the index of the current character.
            map.put(ch, i);

            if (count > maxUniqueSequenceCount) {
                maxUniqueSequenceCount = count;
                maxStartIndex = startingIndex;
                maxEndIndex = i;
            }
        }

        System.out.println(maxUniqueSequenceCount);
        return str.substring(maxStartIndex, maxEndIndex + 1);
    }
}


You may also like to see


Sort Linked list using Merge sort

Bubble Sort

Heap Sort

Selection Sort

Insertion Sort


How ConcurrentHashMap works and ConcurrentHashMap interview questions

How Much Water Can A Bar Graph with different heights can Hold

Interview Questions-Answer Bank



Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.

Post a Comment