Untitled

==========Q1===========
class Solution {
public:
    vector<int> toggleLightBulbs(vector<int>& bulbs) {
        vector<int> switch_(101,0);
        for(int bulb:bulbs){
            switch_[bulb]^=1; // 0=>1, 1=>0
        }
        vector<int> switch_on;
        for(int i=1;i<=100;i++){
            if(switch_[i]==1) switch_on.push_back(i);
        }
        return switch_on;
    }
};

==========Q2===========
class Solution {
public:
    int firstUniqueFreq(vector<int>& nums) {
        unordered_map<int,int> freq,freq_freq;
        for(int num:nums) freq[num]++;
        for(auto [x,f]:freq){
            freq_freq[f]++;
        }
        for(int num:nums){
            int f=freq[num];
            if(freq_freq[f]==1) return num;
        }
        return -1;
    }
};

==========Q3===========
class Solution {
public:
    int almostPalindromic(string s) {
        int n=s.size();
        if(n<=1) return 0;
        auto expand=[&](int left,int right){
            while(left>=0 && right<n){
                if(s[left]==s[right]){
                    left--;
                    right++;
                }
                else{
                    int l1=left-1,r1=right; // remove left character
                    while(l1>=0 && r1<n && s[l1]==s[r1]){
                        l1--;
                        r1++;
                    }
                    int l2=left,r2=right+1; // remove right character
                    while(l2>=0 && r2<n && s[l2]==s[r2]){
                        l2--;
                        r2++;
                    }
                    return max(r1-l1-1,r2-l2-1);
                }
            }
            if(left<0 && right>=n) return right-left-1; // "abba" , "cabba"
            return right-left;
        };
        int longest=0;
        for(int i=0;i<n;i++){
            longest=max(longest,expand(i,i)); // odd length substring
            longest=max(longest,expand(i,i+1)); // even length substring
        }
        return longest;
    }
};

==========Q4===========
class Solution {
    struct Trie{
        struct Node{
            Node* child[2]={nullptr,nullptr};
            int cnt=0;
        };
        Node* root=new Node();
        void insert(int num){
            Node* node=root;
            for(int i=31;i>=0;i--){
                int b=(num>>i)&1;
                if(!node->child[b]) node->child[b]=new Node();
                node=node->child[b];
                node->cnt++;
            }
        }
        void remove(int num){
            Node* node=root;
            for(int i=31;i>=0;i--){
                int b=(num>>i)&1;
                node=node->child[b];
                node->cnt--;
            }
        }
        int query(int num){
            Node* node=root;
            int ans=0;
            for(int i=31;i>=0;i--){
                int b=(num>>i)&1;
                if(node->child[1-b]&&node->child[1-b]->cnt>0){
                    ans|=(1<<i);
                    node=node->child[1-b];
                }else node=node->child[b];
            }
            return ans;
        }
    };
public:
    int maxXor(vector<int>& nums,int k){
        int n=nums.size();
        vector<int> pref(n+1,0);
        for(int i=0;i<n;i++) pref[i+1]=pref[i]^nums[i];
        deque<int> minq,maxq;
        Trie trie;
        int l=0,ans=0;
        trie.insert(pref[0]);
        for(int r=0;r<n;r++){ // l=0,r=0 initially
            while(!minq.empty() && nums[minq.back()]>=nums[r]) minq.pop_back();
            while(!maxq.empty() && nums[maxq.back()]<=nums[r]) maxq.pop_back();
            minq.push_back(r);
            maxq.push_back(r);
            while(nums[maxq.front()]-nums[minq.front()]>k){
                if(minq.front()==l) minq.pop_front();
                if(maxq.front()==l) maxq.pop_front();
                trie.remove(pref[l]);
                l++;
            }
            ans=max(ans,trie.query(pref[r+1]));
            trie.insert(pref[r+1]);
        }
        return ans;
    }
};