class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) return false;

        unordered_map<char, int> countMap;

        // Count frequency of each character in string s
        for (char c : s) {
            countMap[c]++;
        }

        // Subtract frequency of each character in string t
        for (char c : t) {
            countMap[c]--;
            if (countMap[c] < 0) {
                return false;
            }
        }

        return true;
    }
};

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int,int> frequencyMap;

        // Count the frequency of each number
        for (int num : nums) {
            frequencyMap[num]++;
        }

        // Use a max-heap (priority queue) to keep track of top k frequent elements
        priority_queue<pair<int,int>, vector<pair<int,int>>, less<pair<int,int>>> maxHeap;

        for (const auto& entry : frequencyMap) {
            maxHeap.push({entry.second, entry.first});
        }

        // Extract the top k frequent elements from the heap
        vector<int> result;
        for(int i = 0; i < k; ++i) {
            result.push_back(maxHeap.top().second);
            maxHeap.pop();
        }

        return result;
    }
};

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        // Step 1: Count the frequency of each word
        map<string, int> frequency;
        for (const string& word : words) {
            frequency[word]++;
        }

        // Step 2: Create a min-heap using a priority queue
        auto cmp = [](const pair<int, string>& a, const pair<int, string>& b) {
            if (a.first != b.first) {
                return a.first > b.first; // Min-heap based on frequency (reversed for min-heap)
            }
            return a.second < b.second; // Lexicographical order for tie
        };
        priority_queue<pair<int, string>, vector<pair<int, string>>, decltype(cmp)> minHeap(cmp);

        // Step 3: Insert elements into the min-heap
        for (const auto& entry : frequency) {
            minHeap.push({entry.second, entry.first});
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }

        // Step 4: Extract elements from the heap and store in the result vector
        vector<string> result;
        while (!minHeap.empty()) {
            result.push_back(minHeap.top().second);
            minHeap.pop();
        }

        // Since we want the result in lexicographical order, reverse the vector
        reverse(result.begin(), result.end());

        return result;

    }
};

class Solution {
public:
    string frequencySort(string s) {
        // Step 1: Count the frequency of each character
        map<char, int> frequencyMap;
        for (char c : s) {
            frequencyMap[c]++;
        }

        // Step 2: Create a max-heap using a priority queue
        auto comp = [](const auto& a, const auto& b) {
            if (a.first != b.first) {
                return a.first < b.first; // Max-heap based on frequency
            }
            return a.second < b.second; // Lexicographical order for tie
        };
        priority_queue<pair<int, char>, vector<pair<int, char>>, decltype(comp)> maxHeap(comp);

        // Step 3: Insert elements into the max-heap
        for (const auto& entry : frequencyMap) {
            maxHeap.push({entry.second, entry.first});
        }

        // Step 4: Construct the result string
        string result;
        while (!maxHeap.empty()) {
            int freq = maxHeap.top().first;
            char ch = maxHeap.top().second;
            for (int i = 0; i < freq; ++i) {
                result += ch;
            }
            maxHeap.pop();
        }

        return result;
    }
};

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        // Step 1: Use a map to track the frequency of each number
        map<int, int> frequencyMap;
        for (int num : nums) {
            frequencyMap[num]++;
            // Step 2: If any number appears more than once, return true
            if (frequencyMap[num] > 1) {
                return true;
            }
        }

        // Step 3: If no duplicates are found, return false
        return false;
    }
};

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> indexMap;

        for (int i = 0; i < nums.size(); ++i) {
            int num = nums[i];

            // Check if the number exists in the map and the distance is within k
            if (indexMap.find(num) != indexMap.end() && i - indexMap[num] <= k) {
                return true;
            }

            // Update the index of the current number
            indexMap[num] = i;
        }

        return false;
    }
};

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1(nums1.begin(), nums1.end());
        unordered_set<int> resultSet;

        for (int num : nums2) {
            if (set1.find(num) != set1.end()) {
                resultSet.insert(num);
            }
        }

        return vector<int>(resultSet.begin(), resultSet.end());
    }
};

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> countMap;
        vector<int> result;

        // Count the occurrences of each number in nums1
        for (int num : nums1) {
            countMap[num]++;
        }

        // Find the intersection with nums2
        for (int num : nums2) {
            if (countMap[num] > 0) {
                result.push_back(num);
                countMap[num]--;
            }
        }

        return result;
    }
};

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> charCount;

        // Count the frequency of each character in the magazine
        for (char c : magazine) {
            charCount[c]++;
        }

        // Check if the ransom note can be constructed
        for (char c : ransomNote) {
            if (charCount[c] == 0) {
                return false;
            }
            charCount[c]--;
        }

        return true;
    }
};