(LeetCode Problem) lengthOfLongestSubstring (Sliding Windows Algorithm)

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

/** 
* Main class to test the longest substring without repeating characters. 
*/
public class Main {    
    public static void main(String[] args) {        
        ImplClass implObj = new ImplClass();        
        String input = "abcbcbc";        
        System.out.println("Longest unique substring length: " + implObj.implMethod(input));    
    }
}

/** 
* Implementation class containing the algorithm. 
*/
class ImplClass {    
    public ImplClass() {        
    // Default constructor 
    }    

    /**     
    * Finds the length of the longest substring without repeating characters.     
    *     
    * @param s the input string     
    * @return the length of the longest unique substring     
    */ 
    public int implMethod(String s) {        
        if (s == null) {            
        return 0;        
        }   
 
        int maxLength = 0;        
        int left = 0;        
        Map<Character, Integer> count = new HashMap<>();   
 
        for (int right = 0; right < s.length(); right++) {            
            char c = s.charAt(right);            
            count.put(c, count.getOrDefault(c, 0) + 1);            
            // Shrink the window until there are no duplicates 
            while (count.get(c) > 1) {                
                char leftChar = s.charAt(left);                
                count.put(leftChar, count.get(leftChar) - 1);                
                left++;            
            }            
            maxLength = Math.max(maxLength, right - left + 1);        
        }        
        return maxLength;    
    }
}

How the while loop works when a duplicated character is read step-by-step.​

Code Recap

while (count.get(c) > 1) {    
    char leftChar = s.charAt(left);    
    count.put(leftChar, count.get(leftChar) - 1);    
    left++;
}

Purpose

This while loop is part of the sliding window algorithm.
It ensures that the current substring (from left to right) always contains unique characters.

How It Works

1. Duplicate Detected
   When count.get(c) > 1, it means the character c (just read at right) already exists in the current window.

2. Shrink the Window
   The loop moves left forward, one character at a time, removing characters from the count map until the duplicate is gone.

3. Repeat Until Valid
   The loop continues until count.get(c) == 1, meaning there’s only one occurrence of c in the window.

​Example Walkthrough ("abcbcbc")

Why while Instead of if

• if → would remove only one character, possibly leaving duplicates in the window.
• while → keeps removing from the left until all duplicates are gone.

Debug Version

If you want to see it in action:

for (int right = 0; right < s.length(); right++) { 
    char c = s.charAt(right); 
 count.put(c, count.getOrDefault(c, 0) + 1); 


    while (count.get(c) > 1) {  
        System.out.println("Duplicate found: " + c);  
        System.out.println("Current Map: " + count);  
        char leftChar = s.charAt(left);    
        System.out.println("Before Removing: " + count);
        count.put(leftChar, count.get(leftChar) - 1);    
        System.out.println("Removing: " + count);
        left++;
    }
}

This is how the output will be for visualizing the action

Map before put: {}Map after put: {a=1}Map before put: {a=1}Map after put: {a=1, b=1}Map before put: {a=1, b=1}Map after put: {a=1, b=1, c=1}Map before put: {a=1, b=1, c=1}Map after put: {a=1, b=2, c=1}Duplicate found: bCurrent Map: {a=1, b=2, c=1}Before Removing: a, count: {a=1, b=2, c=1}Removing: a, count: {a=0, b=2, c=1}Duplicate found: bCurrent Map: {a=0, b=2, c=1}Before Removing: b, count: {a=0, b=2, c=1}Removing: b, count: {a=0, b=1, c=1}Map before put: {a=0, b=1, c=1}Map after put: {a=0, b=1, c=2}Duplicate found: cCurrent Map: {a=0, b=1, c=2}Before Removing: c, count: {a=0, b=1, c=2}Removing: c, count: {a=0, b=1, c=1}Map before put: {a=0, b=1, c=1}Map after put: {a=0, b=2, c=1}Duplicate found: bCurrent Map: {a=0, b=2, c=1}Before Removing: b, count: {a=0, b=2, c=1}Removing: b, count: {a=0, b=1, c=1}Map before put: {a=0, b=1, c=1}Map after put: {a=0, b=1, c=2}Duplicate found: cCurrent Map: {a=0, b=1, c=2}Before Removing: c, count: {a=0, b=1, c=2}Removing: c, count: {a=0, b=1, c=1}
Longest unique substring length:3​​

Improved Version

Map cleanup: When a character count reaches 0, we can remove it from the map to keep it clean.

Null and empty string handling: Currently, null returns 0, but empty strings should also return 0.

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

public class Main {    
    public static void main(String[] args) {        
        ImplClass implObj = new ImplClass();        
        System.out.println(implObj.implMethod("abcbcbc")); // Expected output: 3 ("abc") 
    }
}

class ImplClass {    
    public ImplClass() {}  
 
    /**     
    * Finds the length of the longest substring without repeating characters.     
    * @param s Input string     
    * @return Length of the longest substring without repeating characters     
    */ 
    public int implMethod(String s) {        
        if (s == null || s.isEmpty()) {            
            return 0;        
        }        

        int maxLength = 0;        
        int left = 0;        
        Map<Character, Integer> charCount = new HashMap<>();  
 
        for (int right = 0; right < s.length(); right++) {            
            char c = s.charAt(right);            
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);  
              
            // Shrink window until no duplicates 
            while (charCount.get(c) > 1) {                
                char leftChar = s.charAt(left);                
                charCount.put(leftChar, charCount.get(leftChar) - 1);                
                if (charCount.get(leftChar) == 0) {                    
                    charCount.remove(leftChar);                
                }                
                left++;            
            }         
       
            maxLength = Math.max(maxLength, right - left + 1);        
        }        
    
        return maxLength;    

    }
}

Changes for Co

how while loop works when duplicated char is read?

Example Walkthrough — "abcbcbc"

How to Read This Table

​count map before while → state of the frequency map right after adding the new character at right.

• Action in while loop → which characters are removed (and decremented) while duplicates exist.
• count map after while → state of the map after duplicates are removed.
• left after → new position of the left pointer after shrinking.

Key Observations

• maxLength increases only when the current window length (right - left + 1) is greater than the previous maximum.
• At Step 2, we hit the longest substring "abc" with length 3.
• After that, duplicates force the window to shrink, so maxLength stays at 3.