How to Find the Longest Substring Without Repeating Characters in Java

When solving the problem of finding the longest substring without repeating characters in Java, the goal is to identify a substring (a contiguous block of characters) where no characters repeat. This is a common interview question that tests your understanding of strings, hashmaps, and sliding window techniques.

Given a string, we need to determine the length of the longest substring that contains no repeated characters. For example:

• Input: "abcabcbb"
• Output: 3 (The longest substring is "abc".)

Sliding Window Technique

The sliding window technique is optimal for this problem. Instead of checking all possible substrings (which can be very slow), we use two pointers to define a window that expands or shrinks as we iterate through the string.

1. Start both pointers at the beginning of the string. One pointer (start) marks the beginning of the current substring, and the other (end) expands to include new characters.
2. Use a HashMap to store the characters and their indices. This helps quickly check if a character has been seen before within the current window.
3. If a character is not in the HashMap, add it and move the end pointer. If a character is already in the HashMap, move the start pointer to exclude the previous occurrence of the character.
4. Continuously calculate the length of the current window and keep track of the maximum length.

import java.util.HashMap;

public class LongestSubstring {
    public static int findLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        HashMap<Character, Integer> map = new HashMap<>();
        int maxLength = 0;
        int start = 0;

        for (int end = 0; end < s.length(); end++) {
            char currentChar = s.charAt(end);

            // If the character is already in the map, move the start pointer
            if (map.containsKey(currentChar)) {
                start = Math.max(start, map.get(currentChar) + 1);
            }

            // Add the character and its index to the map
            map.put(currentChar, end);

            // Calculate the maximum length
            maxLength = Math.max(maxLength, end - start + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        String input = "abcabcbb";
        System.out.println("The length of the longest substring without repeating characters is: " + findLongestSubstring(input));
    }
}

This approach ensures efficiency and simplicity. By using the sliding window and hashmap together, we avoid unnecessary computations and achieve an optimal solution to the problem.