Sliding Window

Longest substring without repeating characters

Rajeev SinghAlgorithms1 mins read

Longest substring without repeating characters

Problem Statement

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "aababcbb"
Output: 3
Explanation: The longest substring without repeating characters is "abc".

Example 2:

Input: s = "cccc"
Output: 1
Explanation: The longest substring without repeating characters is "c".

Example 3:

Input: s = ""
Output: 0

Solution

This problem is similar to the previous problem Longest Substring with K distinct characters.

Finding the Longest substring without repeating characters is same as finding the Longest substring with All distinct characters. So instead of K distinct characters we have to find the longest substring where all characters are distinct.

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

class LongestSubstringWithoutRepeatingCharacters {
    // Variant of Longest Substring with K unique characters
    // Here it is Longest substring with ALL unique characters 
    // (So compare against the whole window length windowEnd-windowStart+1 instead of k)
    private static int findLengthOfLongestSubstringWithoutRepeatingCharacters(String s) {
        int n = s.length();

        int maxLen = -1; // Stores the length of the longest substring without repeating characters found so far.
        Map<Character, Integer> windowCharCount = new HashMap<>(); // Stores the character count for each character in the current window
        int windowStart = 0;

        for(int windowEnd = 0; windowEnd < n; windowEnd++) {
            char c = s.charAt(windowEnd);
            windowCharCount.put(c, windowCharCount.getOrDefault(c, 0) + 1);

            // Shrink the window until all the characters in the window are unique
            while(windowCharCount.size() < windowEnd-windowStart+1) {
                char leftChar = s.charAt(windowStart);

                // Discard the character at windowStart since we're gonna move it out of the window now.
                windowCharCount.put(leftChar, windowCharCount.get(leftChar) - 1);
                if(windowCharCount.get(leftChar) == 0) {
                    windowCharCount.remove(leftChar);
                }

                windowStart++; // Shrink the window                
            }

            // We have a window where all the characters are unique. Update the max length
            if(windowCharCount.size() == windowEnd-windowStart+1) {
                maxLen = Math.max(maxLen, windowEnd-windowStart+1);
            }
        }

        return maxLen;  
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        String s = keyboard.next();
        keyboard.close();
        
        System.out.printf("Longest substring without repeating characters = %d%n", findLengthOfLongestSubstringWithoutRepeatingCharacters(s));
    }
}