/*
   LeetCode 76. Minimum Window Substring

   Hard

   Given two strings s and t of lengths m and n respectively, return
   the minimum window substring of s such that every character in t
   (including duplicates) is included in the window. If there is no
   such substring, return the empty string "".

   The testcases will be generated such that the answer is unique.

   Example 1:
   Input: s = "ADOBECODEBANC", t = "ABC"
   Output: "BANC"
   Explanation: The minimum window substring "BANC" includes 'A', 'B',
   and 'C' from string t.
    
   Example 2:
   Input: s = "a", t = "a"
   Output: "a"
   Explanation: The entire string s is the minimum window.
    
   Example 3:
   Input: s = "a", t = "aa"
   Output: ""
   Explanation: Both 'a's from t must be included in the window.
   Since the largest window of s only has one 'a', return empty string.

   Constraints:

   m == s.length
   n == t.length
   1 <= m, n <= 105
   s and t consist of uppercase and lowercase English letters.

   Hint 1
   Use two pointers to create a window of letters in s, which would
   have all the characters from t.

   Hint 2
   Expand the right pointer until all the characters of t are covered.

   Hint 3
   Once all the characters are covered, move the left pointer and
   ensure that all the characters are still covered to minimize the
   subarray size.

   Hint 4
   Continue expanding the right and left pointers until you reach the end of s.

   Follow up: Could you find an algorithm that runs in O(m + n) time?

   Core Idea: Use a dynamic (variable-size) window [left, right] over s.

   1. Expand right to add characters until the window contains all required characters from t (with correct multiplicities).

   2. Once valid, shrink from left as much as possible while keeping the window valid → this gives a candidate minimum.

   3. Repeat until right reaches the end.

   4. Track the smallest window found

   Key variables
     * need[128] or unordered_map — required count for each char in t
  
     * window[128] — current count in [left, right]
  
     * formed / have — how many unique chars from t are fully satisfied
         (count matches or exceeds need)
  
     * required — total unique chars in t (usually t.size() if
        duplicates, but actually number of distinct keys)
  
     * Track minLen + start index for the best window

   GeeksForGeeks
  [Expected Approach] Using Window Sliding - O(n) Time and O(1) Space:

   The idea is to use Window Sliding (start and j) to maintain a
   sliding window over string S, while tracking character frequencies
   with two count arrays.

   Steps:

   Initialize:
   A count array to store the frequency of characters in P.
   Another count array to track the characters in the current window of S.
   Variables to track the minimum window length and its start index.
   Expand the Window:
   Move the j pointer through S, updating the window's character counts.
   When all characters of P are present in the window, a valid window is found.
   Shrink the Window before updating result
   Move the start pointer right to minimize the window while ensuring all characters from P remain in the window.
   Track the smallest window during this process.
   Return Result:
   If a valid window is found, return the smallest substring. If no
   valid window exists, return "-1".
*/

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

using namespace std;

class Solution {
public:
    string minWindowBruteForce(string s, string t)
    {
        // O(n-squared) check every substring
        //
        // ADOBECODEBANC  ABC

        unordered_map<char,int> t_map;

        for (char c: t) t_map[c]++;
        
        [[maybe_unused]] auto xxx = [&](const string& substring) -> string
        {
            unordered_map<char, int> map;
            
            for (char c: substring)
                map[c]++;

            for (auto& [c, count]: t_map)
            {
                if (auto iter = map.find(c); iter != map.end())
                {                    
                    if (iter->second == count)
                        continue;
                    else
                        return "";                    
                }
                else
                    return "";
            }
            return substring;
        };

        auto hasAllChars = [&](const string& substring) -> bool
        {
            int count[256] = {0};
            
            // Count the frequency of each 
            // character in the pattern
            for (int ch : t)
                count[ch]++;
            
            // For each character in the substring, 
            // decrement its count
            for (int ch : substring) {
                if (count[ch] > 0)
                    count[ch]--;
            }
            
            // If all counts in the count array are zero,
            // the substring contains all characters of the pattern
            for (int i = 0; i < 256; i++) {
                if (count[i] > 0)
                    return false;
            }
            return true;
        };            
        //=======================================================
        
        int minLen = INT_MAX;
        string res = "";

        for (size_t i = 0; i < s.size(); i++)
        {
            for (size_t j = i; j < s.size(); j++)
            {
                string sub = s.substr(i, j - i + 1);
                
                if (hasAllChars(sub))
                {                    
                    cout << sub << endl;
                    int currLen = sub.length();
                    if (currLen < minLen)
                    {                        
                        minLen = currLen;
                        res = sub;
                    }                    
                }                
            }
        }
        return res;        
    }

    void print(unordered_map<char,int>& cnt, string s, int right, int left)
    {
        cout << "charCountMap: " << s << format(" left: {} right: {}\n", left, right);
        for (const auto& [k,v]: cnt) cout << format("{:>4} ", k);
        cout << endl;        
        for (const auto& [k,v]: cnt) cout << format("{:>4} ", v);
        cout << endl;        
    }
    
    string minWindowOneMap(string s, string t)
    {
        unordered_map<char,int> cnt;
        
        for (char c : t) cnt[c]++;
        
        int left = 0, minStart = 0, minLen = INT_MAX, count = t.size();

        print(cnt, s, 0, left);
        
        for (int right = 0; right < (int) s.size(); ++right)
        {
            if (cnt[s[right]]-- > 0) { count--; } print(cnt, s, right, left);  // still needed this char
            
            while (count == 0)
            {
                if (right - left + 1 < minLen)
                {
                    minLen = right - left + 1;

                    minStart = left;
                }
                if (cnt[s[left]]++ == 0) count++;   // now missing this char again
                left++;
            }
        }
        return minLen == INT_MAX ? "" : s.substr(minStart, minLen);
    }

    /*
     Optimal Approach: Sliding Window + Two Frequency Maps (O(m + n) Time)

     This is a classic variable-size sliding window problem.
     Key Idea:
       1. Use a frequency map (need) for characters in t.
       2. Use another map (have) for the current window in s.
       3. Maintain a counter valid = how many unique characters in the window satisfy the required count from t.
       4. Expand the right pointer to include characters.
       5. When the window is valid (valid == need.size()), try to shrink from the left while keeping
            it valid, and track the minimum length window.
     
    */
    
    string minWindowTwoMaps(string s, string t)
    {
        if (s.empty() || t.empty() || s.length() < t.length()) {
            return "";
        }
        
        // Frequency map for t (what we need)
        unordered_map<char, int> need;
        for (char c : t) {
            need[c]++;
        }
        
        // Frequency map for current window
        unordered_map<char, int> have;
        
        int left = 0;
        int minLen = INT_MAX;
        int minStart = 0;
        int valid = 0;  // how many characters are fully satisfied
        
        for (int right = 0; right < (int) s.length(); ++right)
        {
            char c = s[right];
            have[c]++;
            
            // If this character is needed and we now have exactly the required count
            if (need.count(c) && have[c] == need[c]) {
                valid++;
            }
            
            // Try to shrink the window from left as much as possible
            while (valid == (int) need.size() && left <= right) {
                // Update minimum window
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minStart = left;
                }
                
                // Remove left character
                char leftChar = s[left];
                have[leftChar]--;
                
                if (need.count(leftChar) && have[leftChar] < need[leftChar]) {
                    valid--;
                }
                
                left++;
            }
        }
        
        return (minLen == INT_MAX) ? "" : s.substr(minStart, minLen);        
    }    
    

    string minWindowGFG(string s, string t)
    {
        int len1 = s.length(); int len2 = t.length();

        if (len1 < len2) return "";
        
        vector<int> countS(256, 0); vector<int> countT(256, 0);
        
        // Store occurrence of characters of T
        for (int i = 0; i < len2; i++) countT[t[i]]++;
        
        int start = 0, start_idx = -1, min_len = INT_MAX;
        
        int count = 0;
        
        for (int j = 0; j < len1; j++) {
            // Count occurrence of characters of string S
            countS[s[j]]++;
            
            // If S's char matches with T's char, increment count
            if (countT[s[j]] != 0 && countS[s[j]] <= countT[s[j]])
            {
                count++;
            }
            
            // If all characters are matched
            if (count == len2)
            {
                // Try to minimize the window
                while (countS[s[start]] > countT[s[start]] || countT[s[start]] == 0)
                {
                    if (countS[s[start]] > countT[s[start]])
                    {
                        countS[s[start]]--;
                    }
                    start++;
                }
                
                // Update window size
                int len = j - start + 1;
                if (min_len > len)
                {
                    min_len = len;
                    start_idx = start;
                }
            }
        }
        
        if (start_idx == -1)
            return "";
        
        return s.substr(start_idx, min_len);
    }
};

int main(void)
{
    vector<tuple<string, string, string>> testCases = {
        // s                   t      expected
        { "ADOBECODEBANC",    "ABC", "BANC" },
    };

    Solution s;
    
    for (const auto& testCase: testCases)
    {
        string result = s.minWindowOneMap(get<0>(testCase), get<1>(testCase));
        cout << format("s: {} t: {} expected: {} result: {}\n",
                       get<0>(testCase),
                       get<1>(testCase),
                       get<2>(testCase),
                       result);

        // result = s.minWindowGFG(get<0>(testCase), get<1>(testCase));
        // cout << format("s: {} t: {} expected: {} result: {}\n",
        //                get<0>(testCase),
        //                get<1>(testCase),
        //                get<2>(testCase),
        //                result);

        // string result = s.minWindowBruteForce(get<0>(testCase), get<1>(testCase));
        // cout << format("s: {} t: {} expected: {} result: {}\n",
        //                get<0>(testCase),
        //                get<1>(testCase),
        //                get<2>(testCase),
        //                result);

    }
}