3. Longest Substring Without Repeating Characters

Intitution

The problem asks for the length of the longest substring with no repeating characters. We can approach this by using the sliding window technique. As we traverse the string, we maintain a window of characters with no duplicates. When we encounter a duplicate, we shrink the window from the left until the duplicate is removed. Throughout, we keep track of the maximum window size observed.

Complexity

Space Complexity	Time Complexity
$\text{O}(N)$	$\text{O}(N)$

Code

public int lengthOfLongestSubstring(String input) {
    // Array to keep track of seen characters in the current window
    boolean[] isCharSeen = new boolean[256];

    int maxSubstringLength = 0;

    // Sliding window boundaries
    for (int windowStart = 0, windowEnd = 0; windowEnd < input.length(); ++windowEnd) {
        // If character at windowEnd has already been seen, shrink the window from the start
        while (isCharSeen[input.charAt(windowEnd) - '\0'] && windowStart < windowEnd) {
            isCharSeen[input.charAt(windowStart++) - '\0'] = false;
        }

        // Update the maximum length if this window is longer
        maxSubstringLength = Math.max(windowEnd - windowStart + 1, maxSubstringLength);

        // Mark the current character as seen
        isCharSeen[input.charAt(windowEnd) - '\0'] = true;
    }

    return maxSubstringLength;
}