Longest Substring Without Repeating Characters - LeetCode

// Longest Substring Without Repeating Characters - https://leetcode.com/problems/longest-substring-without-repeating-characters/description/?source=submission-ac

class Solution {

    // Time Complexity: O(N^2)
    // Space Complexity; O(k)
    //  where k is the length of longest substring
    // public int lengthOfLongestSubstring(String s) {

    //     int maxLength = 0;
    //     for(int i = 0; i < s.length(); i++) {
    //         Set<Character> set = new HashSet<>();

    //         set.add(s.charAt(i));
    //         int currentLength = 1;

    //         for(int j = i + 1; j < s.length(); j++) {
    //             if(set.contains(s.charAt(j))) {
    //                 break;
    //             }
    //             set.add(s.charAt(j));
    //             currentLength++;
    //         }

    //         if(currentLength > maxLength) {
    //             maxLength = currentLength;
    //         }
    //     }

    //     return maxLength;
    // }

    // Time Complexity: O(n)
    // Space Complexity: O(k)
    //  where n is the string length
    //  and k is the size of the character set
    // public int lengthOfLongestSubstring(String s) {
    //     Set<Character> window = new HashSet<>();

    //     int left = 0, right = 0, maxLength = 0;
    //     for(; right < s.length(); right++) {
    //         Character c = s.charAt(right);

    //         while(window.contains(c)) {
    //             window.remove(s.charAt(left));
    //             left++;
    //         }

    //         window.add(c);
    //         maxLength = Math.max(maxLength, right - left + 1);
    //     }

    //     return maxLength;
    // }

    // Time Complexity: O(n)
    // Space Complexity: O(k)
    //  where k is the size of the character set
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        // Assuming ASCII character set (128 characters)
        // We store the last index where we saw each character.
        int[] lastSeenIndex = new int[128];
        Arrays.fill(lastSeenIndex, -1); // -1 means "not seen yet"

        int maxLength = 0;
        int left = 0; // The left boundary of the sliding window

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);

            // Check if the character was seen before and if its last
            // occurrence is inside our current window [left, right].
            if (lastSeenIndex[c] >= left) {
                // Duplicate found in the window.
                // Move the left pointer to the position after the last occurrence.
                left = lastSeenIndex[c] + 1;
            }

            // Update the last seen index for this character to the current position.
            lastSeenIndex[c] = right;

            // Calculate the length of the current window and update max.
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}