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.