/*
   Leet 3. Longest Substring Without Repeating Characters

   Given a string s, find the length of the longest substring without duplicate characters.
    
   Example 1:
   Input: s = "abcabcbb"
   Output: 3
   Explanation: The answer is "abc", with the length of 3. Note that "bca" and "cab" are also correct answers.
    
   Example 2:
   Input: s = "bbbbb"
   Output: 1
   Explanation: The answer is "b", with the length of 1.
   Example 3:

   Input: s = "pwwkew"
   Output: 3
   Explanation: The answer is "wke", with the length of 3.
   Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
    
   Constraints:

   0 <= s.length <= 5 * 104
   s consists of English letters, digits, symbols and spaces.

   Optimal Solution – Sliding Window with Hash Map (O(n) time)
   
   Key Interview Talking Points (say these out loud)
     * Time Complexity: O(n) – we visit each character at most twice
     * Space Complexity: O(min(m, n)) where m = charset size (usually 128 or 256 for ASCII)
                → in practice we say O(1) if we assume fixed alphabet size
     * Why unordered_map instead of map? → average O(1) vs O(log 256)

     Follow-up questions Bloomberg-style interviewers love

     What if the string contains Unicode characters?
        → Use unordered_map<char32_t, int> or std::map or handle UTF-8 properly
     Can you do it without extra space beyond O(1)?
        → No (unless alphabet is very small and fixed)
     Modify to return the substring itself, not just length
        → Keep track of best start index + length
     What if we want the lexicographically smallest among all longest substrings?
        → Need to track all candidates or scan again


 Optimal Approach: Sliding Window + Frequency Map (O(n) time, O(1)  space)         
   * Use two pointers (left, right) to maintain a valid window [left, right] with no duplicates.
   * Expand right pointer, add s[right] to a frequency count.
   * If s[right] count > 1 (duplicate found), shrink from left until no duplicate.
   * At every step, update max_length = max(max_length, right - left + 1)

  Since characters are limited (ASCII), we use a fixed-size array int count[128] = {0}; → O(1)  space.
  
  This is the classic variable-size sliding window for "longest substring with constraint".

  Why O(n)? Each character is added once (right moves n times) and removed at most once (left moves at most n times total). Amortized O(1) per character.        
*/

#include <bits/stdc++.h>
#include <gtest/gtest.h>

using namespace std;

class Solution
{
public:
    int lengthOfLongestSubstringTwoLoops(string s) {

        int maxLen = 0;
        
        for (size_t outer = 0; outer < s.size(); outer++)
        {
            vector<bool> seen(26, false);
            int localMax = 0;            
            
            for (size_t inner = outer; inner < s.size(); inner++)
            {
                if (seen[s.at(inner) - 'a'])
                    break;

                localMax += 1;
                seen[s.at(inner) - 'a'] = true;
            }

            maxLen = max(maxLen, localMax);
        }
        
        return maxLen;
    }

    // Bloomberg expects Sliding Window with Hash Map (O(n) time)
    // Two pointers - left,right define sliding window
    int lengthOfLongestSubstringSlidingWindow(string s)
    {
        // map of char to lastindex of char
        unordered_map<char, int> charIndexMap;

        int maxLen = 0;
        int left = 0;

        for (int right = 0; right < (int) s.size(); right++)
        {            
            char current_char = s[right];

            // if current char is seen and it's in the current window move left pointer
            if (charIndexMap.contains(current_char) && charIndexMap[current_char] >= left)
            {
                cout << format("  charIndexMap[{}] = {}, left = {} -> left = {}\n", current_char, charIndexMap[current_char], left, left+1);
                left = charIndexMap[current_char] + 1;
            }
            
            charIndexMap[current_char] = right;
            maxLen = max(maxLen, right - left + 1);
            
            cout << "maxLen: " << maxLen << " window left: " << left << " right: " << right << " map: ";
            for (auto& [k,v]: charIndexMap) cout << k << "[" << v << "] ";
            cout << endl;            
        }

        cout << "-----------------" << endl;        
        cout << "maxLen: " << maxLen << " ";
        cout << "window: left: " << left << " map: ";
        for (auto& [k,v]: charIndexMap) cout << k << "[" << v << "] ";
        cout << endl;

        return maxLen;
    }

    //
    // maxL=1     maxL=2    maxL=3     maxL=3     maxL=3
    // 0          0         0          1          2
    // left       left      left       left       left   
    // |          |         |          |          |      
    // v          v         v          v          v      
    // abcabcbb   abcabcbb  abcabcbb  abcabcbb  abcabcbb  ... 
    // ^           ^          ^          ^          ^   
    // |           |          |          |          |   
    // right       right     right      right      right
    // 0           1         2          3          4    
};

struct Solution_xAI
{
    int lengthOfLongestSubstring(std::string s) {
        if (s.empty()) return 0;
        
        // int count[128] = {0};  // ASCII, or 256 for safety
        unordered_map<char, int> count;
        
        int left = 0;
        int maxLen = 0;
        int n = s.length();
        
        for (int right = 0; right < n; ++right) {
            ++count[s[right]];  // add current char
            
            // shrink window from left while duplicate exists
            while (count[s[right]] > 1) {
                --count[s[left]];
                ++left;
            }
            
            maxLen = std::max(maxLen, right - left + 1);
            cout << "maxLen: " << maxLen << " window left: " << left << " right: " << right
                 << " " << s.substr(left, right - left + 1) << endl;
        }
        
        return maxLen;
    }
};
    

int main()
{
    vector<tuple<string, string, int>> testCases = {
        //string           substr     longestSubstr   
        //--------         ------     -------------   
         {"abcabcbb",      "abc",      3},
        // {"bbbbb",         "b"  ,      1},
        // {"pwwkew",        "wke",      3}, 
        // {"abcabcdabcde",  "abcde",    5},
        // {"",              "",         0},
        // {"dvdf",          "vdf",      3},
        // {"anviaj",        "nviaj",    5},
        // {"geeksforgeeks", "eksforg",  7},
        // {"xyxyxwxyz",     "wxyz",     4},
    };

    Solution_xAI s;
    
    for (auto& tc: testCases)
    {
        cout << get<0>(tc) << endl;        
        int len = s.lengthOfLongestSubstring(get<0>(tc));
        cout << "str: " << get<0>(tc) << " actual: " << len
             << " expected: " << get<2>(tc) << " substr: " << get<1>(tc) << endl;
        cout << (len == get<2>(tc) ? "  passed" : "  failed") << endl;
        EXPECT_EQ(get<2>(tc), len);
        cout << "---------------\n";
    }
    
    return 0;
}