package Leetcode.SlideWindow;

import java.util.HashMap;

/**
 * @author zhengstars
 * @date 2024/03/26
 */
public class LongestSubstringWithoutRepeatingCharacters {
    public static int lengthOfLongestSubstring(String s) {
        // We start by initializing a HashMap to keep track of the characters we have encountered
        HashMap<Character, Integer> map = new HashMap<>();

        // 'start' and 'end' pointers represent the current window
        // 'length' holds the maximum length of substring without repeating characters we have found till now.
        int start = 0, end = 0, length = 0;

        // We expand the window by incrementing 'end' and move 'start' as needed
        while (end < s.length()){
            // The current character at the 'end' of the window
            char c = s.charAt(end);

            // If character 'c' has already been encountered, move 'start' pointer to the next position from its previous occurrence
            if(map.containsKey(c)){
                start = Math.max(start, map.get(c) + 1);
            }

            // Update the position of character 'c'
            map.put(c, end);

            // Update the length of the longest substring without repeating characters
            length = Math.max(length, end-start+1);

            // Expand the window
            end++;
        }
        // Finally, return the length of longest substring without repeating characters
        return length;
    }

    public static void main(String[] args) {
        // Test the function with example string "abcabcbb"
        String s1 = "abcabcbb";
        System.out.println(lengthOfLongestSubstring(s1));  // Output: 3

        // Test the function with example string "bbbbb"
        String s2 = "bbbbb";
        System.out.println(lengthOfLongestSubstring(s2));  // Output: 1

        // Test the function with example string "pwwkew"
        String s3 = "pwwkew";
        System.out.println(lengthOfLongestSubstring(s3));  // Output: 3
    }
}