Longest Substring Without Repeating Characters - Java Solution

1. Introduction

In this blog post, we'll explore a common string processing problem: finding the length of the longest substring without repeating characters. This problem is a classic example of the sliding window technique in action.

Problem

Given a string s, find the length of the longest substring that does not contain any repeating characters.

2. Solution Steps

1. Use a sliding window approach to process the string.

2. Maintain a hashmap to keep track of the characters and their most recent indices in the window.

3. Expand the window by adding characters from the right.

4. If a character is repeated, shrink the window from the left until the repeated character is removed.

5. Update the maximum length of the substring as the window changes.

6. Return the maximum length found.

3. Code Program

import java.util.HashMap;

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        System.out.println("Longest substring without repeating: " + lengthOfLongestSubstring("aababcbb"));
        System.out.println("Longest substring without repeating: " + lengthOfLongestSubstring("cccc"));
        System.out.println("Longest substring without repeating: " + lengthOfLongestSubstring(""));
    }

    // Method to find the length of the longest substring without repeating characters
    public static int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> charIndexMap = new HashMap<>();
        int windowStart = 0, maxLength = 0;

        for (int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
            char rightChar = s.charAt(windowEnd);

            // If the character is already in the hashmap, shrink the window from the left
            if (charIndexMap.containsKey(rightChar)) {
                windowStart = Math.max(windowStart, charIndexMap.get(rightChar) + 1);
            }

            charIndexMap.put(rightChar, windowEnd); // Add the character to the hashmap
            maxLength = Math.max(maxLength, windowEnd - windowStart + 1); // Update the maximum length
        }

        return maxLength;
    }
}

Output:

Longest substring without repeating: 3
Longest substring without repeating: 1
Longest substring without repeating: 0

Explanation:

The lengthOfLongestSubstring method implements a sliding window approach with a hashmap to track the indices of characters. It adjusts the window to ensure that no character is repeated. 

For example, in the string "aababcbb", the method finds the longest substring without repeating characters to be "abc" with a length of 3. 

In the case of "cccc", the longest such substring is just a single character "c", hence the length is 1. 

For an empty string, the output is naturally 0.