Leet Code Weekly Contest 292

class Solution {
public:
    string largestGoodInteger(string num) {
        string ans = "";
        for (int i = 0; i + 2 < num.length(); i++) {
            string s = num.substr(i, 3);
            if (s[0] == s[1] && s[1] == s[2] && s > ans) {
                ans = s;
            }
        }
        return ans;
    }
};

class Solution {
private:
    int ans = 0;
    
    pair<int, int> dfs(TreeNode *root) {
        if (root == NULL) {
            return make_pair(0, 0);
        }
        pair<int, int> ret = make_pair(1, root->val);
        auto a = dfs(root->left), b = dfs(root->right);
        ret.first += a.first;
        ret.first += b.first;
        ret.second += a.second;
        ret.second += b.second;
        if (ret.second / ret.first == root->val) {
            ans++;
        }
        return ret;
    }
    
public:
    int averageOfSubtree(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

typedef long long LL;

const LL kMod = 1000000007;

class Solution {
public:
    int countTexts(string pressedKeys) {
        unordered_map<char, LL> maxRep;
        for (char c = '2'; c <= '9'; c++) {
            maxRep[c] = (c == '7' || c == '9') ? 4 : 3;
        }
        LL n = pressedKeys.length();
        vector<vector<LL>> f(5, vector<LL>(n + 1));
        for (LL i = 3; i <= 4; i++) {
            f[i][0] = 1;
            for (LL j = 1; j <= n; j++) {
                f[i][j] = 0;
                for (LL k = j - 1; k >= (j - i) && k >= 0; k--) {
                    f[i][j] += f[i][k];
                }
                f[i][j] %= kMod;
            }
        }
        LL ans = 1;
        for (int i = 0, j; i < pressedKeys.length(); i = j + 1) {
            for (j = i; j + 1 < pressedKeys.length() && pressedKeys[j + 1] == pressedKeys[j]; ) j++;
            ans = (ans * f[maxRep[pressedKeys[i]]][j - i + 1]) % kMod;
        }
        return ans;
    }
};

class Solution {
private:
    bool f[101][101][202];
    
public:
    bool hasValidPath(vector<vector<char>>& grid) {
        int n = grid.size(), m = grid.front().size();
        
        if ((n + m - 1) % 2 != 0) {
            return false;
        }
        
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                for (int lc = 0; lc <= (x + y + 1); lc++) {
                    f[x][y][lc] = false;
                }
            }
        }
        
        f[0][0][1] = grid[0][0] == '(';
        
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                for (int lc = 0; lc <= (x + y + 1); lc++) {
                    if (!f[x][y][lc]) {
                        continue;
                    }
                    int nl = x + y + 2;
                    if (x + 1 < n) {
                        int t = lc + (grid[x + 1][y] == '(');
                        if (t >= nl - t) {
                            f[x + 1][y][t] = true;
                        }
                    }
                    if (y + 1 < m) {
                        int t = lc + (grid[x][y + 1] == '(');
                        if (t >= nl - t) {
                            f[x][y + 1][t] = true;
                        }
                    }
                }
            }
        }
        
        
        return f[n - 1][m - 1][(n + m - 1) / 2];
    }
};