// Longest Substring Without Repeating Characters - https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

class Solution {
    // Brute Force
    // Time Complexity: O(n^2)
    // Space Complexity: O(m) where m is length of longest substring
    // public int lengthOfLongestSubstring(String s) {
    //     int maxLength = 0;

    //     for(int i = 0; i < s.length(); i++) {
    //         int len = 1;
    //         Set set = new HashSet<>();
    //         set.add(s.charAt(i));
    //         for(int j = i+1; j < s.length(); j++) {
    //             if (set.contains(s.charAt(j))) {
    //                 break;
    //             }
    //             else {
    //                 set.add(s.charAt(j));
    //                 len++;
    //             }
    //         }

    //         maxLength = Math.max(len, maxLength);
    //     }
    //     return maxLength;
    // }

    // Sliding Window
    // Time Complexity: O(n)
    // Space Complexity: O(m) where m is length of longest substring
    // public int lengthOfLongestSubstring(String s) {
    //     int maxLength = 0;
    //     int left = 0, right = 0;
    //     Set set = new HashSet<>();
    //     for(int i = 0; i < s.length(); i++) {
    //         while(set.contains(s.charAt(i))) {
    //             set.remove(s.charAt(left));
    //             left++;
    //         } 

    //         set.add(s.charAt(i));
    //         maxLength = Math.max(right - left + 1, maxLength);
    //         right++;
    //     }
    //     return maxLength;
    // }

    // Sliding Window (Optimised)
    // Time Complexity: O(n)
    // Space Complexity: O(m) where m is length of longest substring
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        int left = 0;
        Map map = new HashMap<>();
        for(int right = 0; right < s.length(); right++) {

            if(map.containsKey(s.charAt(right))) {
                left = Math.max(map.get(s.charAt(right)) + 1, left);
            }
            
            map.put(s.charAt(right), right);
            maxLength = Math.max(right - left + 1, maxLength);
        }
        return maxLength;
    }
}