Longest Substring Unique Characters

Jugal Gandhi bio photo By Jugal Gandhi

Queue implementation to find the longest substring inside a string with non-repeating characters.

Time Complexity: O(N)

public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;


        if(s.length() == 0)
            return maxLength;
        if(s.length() == 1)
            return 1;

        int endIndex = 0;
        
        //Keep adding distinct characters to queue
        Queue<Character> subLong = new LinkedList<>();

        while(endIndex < s.length()){
            Character next = s.charAt(endIndex);
            //if the character on next index is already present in queue -> poll the queue
            //until you find the character
            if(subLong.contains(next)){
                while(true){
                    Character curr = subLong.poll();
                    System.out.println("popping: " + curr);
                    if(curr == next){
                        break;
                    }
                }
            }
            //every time keep adding in queue and check the size of queue with maxLength
            subLong.add(next);
            endIndex++;
            maxLength = Math.max(maxLength, subLong.size());
        }
        return maxLength;
    }