---
titile: Biweekly Contest 49
tags: LeetCode Contest
---

[LeeteCode - Biweekly Contest 49](https://leetcode.com/contest/biweekly-contest-49)
===

Q1 - 1812. Determine Color of a Chessboard Square
---

class Solution {
public:
    bool squareIsWhite(string coordinates) {
        return ((coordinates[0] - 'a') + (coordinates[1] - '1')) & 1;
    }
};

Q2 - 1813. Sentence Similarity III
---

class Solution {
public:
    bool areSentencesSimilar(string sentence1, string sentence2) {
        
        vector<string> words1;
        {
            stringstream ss(sentence1);
            string str;
            while(ss >> str){
                words1.push_back(str);
            }
        }
        
        vector<string> words2;
        {
            stringstream ss(sentence2);
            string str;
            while(ss >> str){
                words2.push_back(str);
            }
        }
        
        
        
        if(words1.size() < words2.size()){
            swap(words1, words2);
        }
        
        
        int l = 0, r1 = words1.size() - 1, r2 = words2.size() - 1;
        
        for(;l <= r2 && words1[l] == words2[l]; l++);
        
        for(;l <= r2 && words1[r1] == words2[r2]; r1--, r2--);
        
        
        return  l > r2;
    }
};

Q3 - 1814. Count Nice Pairs in an Array
---

int rev(int num){
    int ret = 0;
    while(num){
        ret = ret * 10 + num % 10;
        num /= 10;
    }
    
    return ret;
}

class Solution {
public:
    int countNicePairs(vector<int>& nums) {
        unordered_map<int, int> revDifs;
        for(int num: nums){
            revDifs[num - rev(num)]++;
        }
        
        const long int MOD = 1e9 + 7;
        long int ret = 0; 
        for(auto revDif: revDifs){
            long int num = revDif.second;
            
            ret = (ret + num * (num-1) / 2) % MOD;
        }
        
        return ret;
    }
};

Q4 - 1815. Maximum Number of Groups Getting Fresh Donuts
---

class Solution {
public:
    int maxHappyGroups(int batchSize, vector<int>& groups) {
        
        int ret = 0;
        vector<char> remainCounts(batchSize);
        for(int group: groups){
            group %= batchSize;
            
            if(group == 0){
                ret++;
            }else if(remainCounts[batchSize - group] > 0){
                remainCounts[batchSize - group]--;
                ret++;
            }else{
                remainCounts[group]++;
            }
        }
        
        
        auto stringKeyCreater = [&](){
            
            string key;
            for(int i  = 1; i < batchSize; i++){
                key.push_back(i);
                key.push_back(':');
                key.push_back(remainCounts[i]);
                key.push_back(',');
            }
            return key;
        };
        
        unordered_map<string, int> status;
        
        
        function<int(int)> dfs = [&](int remain){
            
            string key = stringKeyCreater();
            if(status.count(key)){
                return status[key];
            }
            
            int ret = 0;
            for(int i = 1; i < batchSize; i++){
                
                if(remainCounts[i] == 0){
                    continue;
                }
                
                int cur = remain == 0;
                
                remainCounts[i]--;
                cur += dfs((remain - i + batchSize) % batchSize);
                remainCounts[i]++;
                
                ret = max(ret, cur);
            }
            
            return status[key] = ret;
        };
        
        return ret + dfs(0);
    }
};