3. Longest Substring Without Repeating Characters

#sliding-window

Problem

Longest Substring Without Repeating Characters - LeetCodeLeetCode

Intuition

Time Complexity

Space Complexity

Solution

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // n -> s.length(), length of string
        // Time Complexity: O(n), traverse through string
        // Space Complexity: O(n). for the hashset
        
        // Create a set to track the characters seen in the current substring
        Set<Character> seen = new HashSet<>();
        
        int start = 0; // Start pointer of the substring
        int end = 0; // End pointer of the substring
        int maxLen = 0; // Maximum length of the substring without repeating characters
        
        // Iterate over the string using the end pointer
        for (; end < s.length(); end++) {
            char ch = s.charAt(end);
            
            // If the current character is already seen in the substring
            while (seen.contains(ch)) {
                // Remove characters from the start of the substring until the current character is no longer seen
                seen.remove(s.charAt(start++));
            }
            
            // Add the current character to the set of seen characters
            seen.add(ch);
            
            // Update the maximum length of the substring if necessary
            maxLen = Math.max(maxLen, end - start + 1);
        }
        
        return maxLen;
    }
}