#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;

int lengthofLongestSubString(string s)
{
    int n = s.size(),left = -1, res = 0;
    unordered_set<char>set;
    for(int i = 0; i < n ; ++i)
    {
        if(i != 0)
        {
            set.erase(s[i-1]);
        }
        while(left+1 < n && !set.count(s[left+1]))
        {
            set.insert(s[left+1]);
            ++left;
        }
        res = max(res,left - i + 1);
    }    
    return res;
}


int lengthOfLongestSubstringDistinct(string s)
{
    unordered_map<char,int>map;
    int left = 0, res = 0;
    for(int i = 0; i < s.size(); ++i)
    {
        char cur = s[i];
        ++map[cur];
        while(map.size() > 2)
        {
            char c = s[left];
            --map[c];
            if(map.at(c)==0)map.erase(c);
            ++left;
        }
        res = max(res, i - left + 1);
    }
    return res;
}

int lengthOfLongestSubstringDistinctK(string s,int k)
{
    int left = 0, res = 0;
    unordered_map<char,int>map;
    for(int i = 0; i < s.size(); ++i)
    {
        char cur = s[i];
        ++map[cur];
        while(map.size() > k)
        {
            char c = s[left];
            --map[c];
            if(map[c] == 0)map.erase(c);
            ++left;
        }
        res = max(res, i - left + 1);
    }
    return res;
}

string minWindow(string s, string t)
{
    unordered_map<char,int>map;
    for(char c:t)
    {
        ++map[c];
    }
    int left = 0, minStart = 0, minLen = INT_MAX, cnt = 0;
    for(int i = 0; i < s.size(); ++i)
    {
        char c = s[i];
        if(map.count(c))
        {
            if(map[c]>0)++cnt;
            --map[c];
        }
        while(cnt == t.size())
        {
            if(i - left + 1 < minLen)
            {
                minLen = i - left + 1;
                minStart = left;
            }
            char leftChar = s[left];
            if(map.count(leftChar))
            {
                ++map[leftChar];
                if(map[leftChar] > 0) --cnt;
            }
            ++left;
        }
    }
    if(minLen == INT_MAX)return "";
    return s.substr(minStart,minLen);
}

int longestSubstring(string s, int k)
{
    int res = 0;
    for(int unique = 1; unique <= 26; ++unique)
    {
        unordered_map<char,int>map;
        int left = 0,cnt = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            char c = s[i];
            ++map[c];
            if(map[c] == k)++cnt;
            while(map.size() > unique)
            {
                char leftChar = s[left];
                if(map[leftChar]==k)--cnt;
                --map[leftChar];
                if(map[leftChar] == 0)map.erase(leftChar);
                ++left;
            }
            int count = map.size();
            if(count == unique && count == cnt)res = max(res,i-left+1);
        }
    }
    return res;
}

int minSubArrayLen(int target,const vector<int>& nums)
{
    int left = 0, n = nums.size(),res = INT_MAX, sum = 0;
    for(int i = 0; i < n; ++i)
    {
        sum += nums[i];
        while(sum >= target)
        {
            res = min(res,i - left + 1);
            sum -= nums[left++];
        }
    }
    return res == INT_MAX ? 0 : res;
}

int characterReplace(string s, int k)
{
    int n = s.size();
    vector<int>cnt(26);
    int left = 0, res = 0;
    for(int i = 0; i < n ;++i)
    {
        ++cnt[s[i]-'A'];
        while(i - left + 1 - *max_element(cnt.begin(),cnt.end()) > k)
        {
            --cnt[s[i]-'A'];
            ++left;
        }
        res = max(res,i-left+1);
    }
    return res;
}

int atMost(const vector<int>& nums,int k)
{
    int left = 0, res = 0;
    unordered_map<int,int>map;
    for(int i = 0; i < nums.size(); ++i)
    {
        if(!map.count(nums[i]) || map[nums[i]] == 0)--k;
        ++map[nums[i]];
        while(k < 0)
        {
            --map[nums[left]];
            if(map[nums[left]]== 0) ++k;
            ++left;
        }
        res += i - left + 1;
    }
    return res;
}

int subArraysWithDistinct(const vector<int>&nums,int k)
{
    return atMost(nums,k) - atMost(nums,k-1);
}

int atMost1(const vector<int>&nums,int k)
{
    int res = 0, left = 0, n = nums.size();
    for(int i = 0; i < n; ++i)
    {
        k -= nums[i] % 2;
        while(k < 0) k += nums[left++]%2;
        res += i - left + 1;
    }
    return res;
}

int numberofNiceNumber(const vector<int>& nums,int k)
{
    return atMost1(nums,k) - atMost1(nums,k-1);
}

int main()
{

    //LeetCode3
    string s = "abcabcbb";
    cout << lengthofLongestSubString(s) << endl;

    //LeetCode159
    s = "ccaabbb";
    cout << lengthOfLongestSubstringDistinct(s) << endl;

    //LeetCode340
    s = "aa";
    int k = 1;
    cout << lengthOfLongestSubstringDistinctK(s,k) << endl;

    //LeetCode76
    s = "ADOBECODEBANC";
    string t = "ABC";
    cout << minWindow(s,t) << endl;

    //LeetCode395
    s = "aaabb";
    k = 3;
    cout << longestSubstring(s,k) << endl;

    //LeetCode209
    vector<int>nums{2,3,1,2,4,3};
    int target = 7;
    cout << minSubArrayLen(target,nums) << endl;

    //LeetCode424
    s = "ABAB";
    k = 2;
    cout << characterReplace(s,k) << endl;

    //LeetCode992
    nums = {1,2,1,2,3};
    k = 2;
    cout << subArraysWithDistinct(nums,k) << endl;

    //LeetCode1248
    nums = {1,1,2,1,1};
    k = 3;
    cout << numberofNiceNumber(nums,k) << endl;
    return 0;
}