class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& q) {
        sort(q.begin(), q.end(), [](vector<int> a, vector<int> b) {
            return a[1] < b[1];
        });
        if (q.empty()) return 0;
        int res = 1, r = q[0][1];
        for (int i = 1; i < q.size(); i ++ )
            if (q[i][0] >= r) {
                res ++;
                r = q[i][1];
            }
        return q.size() - res;
    }
};

class Solution {
public:
    int countSegments(string s) {
        int res = 0;
        for (int i = 0; i < s.size(); i ++ ) {
            if (s[i] == ' ') continue;
            int j = i + 1;
            while (j < s.size() && s[j] != ' ') j ++ ;
            res ++ ;
            i = j - 1;
        }
        return res;
    }
};

class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        unordered_set<string> S;
        for (auto& s: bank) S.insert(s);
        unordered_map<string, int> dist;
        queue<string> q;
        q.push(start);
        dist[start] = 0;
        char chrs[4] = {'A', 'T', 'C', 'G'};

        while (q.size()) {
            auto t = q.front();
            q.pop();
            for (int i = 0; i < t.size(); i ++ ) {
                auto s = t;
                for (char c: chrs) {
                    s[i] = c;
                    if (S.count(s) && dist.count(s) == 0) {
                        dist[s] = dist[t] + 1;
                        if (s == end) return dist[s];
                        q.push(s);
                    }
                }
            }
        }
        return -1;
    }
};

class AllOne {
public:
    struct Node {
        Node *left, *right;
        int val;
        unordered_set<string> S;

        Node (int _val) {
            val = _val;
            left = right = NULL;
        }
    }*left, *right;
    unordered_map<string, Node*> hash;

    /** Initialize your data structure here. */
    AllOne() {
        left = new Node(INT_MIN), right = new Node(INT_MAX);
        left->right = right, right->left = left;
    }

    Node* add_to_right(Node* node, string key, int val) {
        if (node->right->val == val) node->right->S.insert(key);
        else {
            auto t = new Node(val);
            t->S.insert(key);
            t->right = node->right, node->right->left = t;
            node->right = t, t->left = node;
        }
        return node->right;
    }

    Node* add_to_left(Node* node, string key, int val) {
        if (node->left->val == val) node->left->S.insert(key);
        else {
            auto t = new Node(val);
            t->S.insert(key);
            t->left = node->left, node->left->right = t;
            node->left = t, t->right = node;
        }
        return node->left;
    }

    void remove(Node* node) {
        node->left->right = node->right;
        node->right->left = node->left;
        delete node;
    }

    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    void inc(string key) {
        if (hash.count(key) == 0) hash[key] = add_to_right(left, key, 1);
        else {
            auto t = hash[key];
            t->S.erase(key);
            hash[key] = add_to_right(t, key, t->val + 1);
            if (t->S.empty()) remove(t);
        }
    }

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        if (hash.count(key) == 0) return;
        auto t = hash[key];
        t->S.erase(key);
        if (t->val > 1) {
            hash[key] = add_to_left(t, key, t->val - 1);
        } else {
            hash.erase(key);
        }
        if (t->S.empty()) remove(t);
    }

    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        if (right->left != left) return *right->left->S.begin();
        return "";
    }

    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        if (left->right != right) return *left->right->S.begin();
        return "";
    }
};

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne* obj = new AllOne();
 * obj->inc(key);
 * obj->dec(key);
 * string param_3 = obj->getMaxKey();
 * string param_4 = obj->getMinKey();
 */

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/

class Solution {
public:
    Node* flatten(Node* head) {
        auto res = dfs(head);
        return res[0];
    }

    vector<Node*> dfs(Node* head) {
        if (!head) return {NULL, NULL};
        auto cur = head, tail = head;
        while (cur) {
            tail = cur;
            if (cur->child) {
                auto t = dfs(cur->child);
                cur->child = NULL;
                t[1]->next = cur->next;
                if (cur->next) cur->next->prev = t[1];
                cur->next = t[0];
                t[0]->prev = cur;
                cur = t[1]->next;
                tail = t[1];
            } else {
                cur = cur->next;
            }
        }
        return {head, tail};
    }
};

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> res;
        if (!root) return res;
        queue<Node*> q;
        q.push(root);
        while (q.size()) {
            int len = q.size();
            vector<int> line;
            while (len -- ) {
                auto t = q.front();
                q.pop();
                line.push_back(t->val);
                for (auto c: t->children) q.push(c);
            }
            res.push_back(line);
        }
        return res;
    }
};

/*
// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;

    Node() {
        val = false;
        isLeaf = false;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }

    Node(bool _val, bool _isLeaf) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }

    Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
*/

class Solution {
public:
    vector<vector<int>> s;


    Node* construct(vector<vector<int>>& w) {
        int n = w.size();
        s = vector<vector<int>>(n + 1, vector<int>(n + 1));
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + w[i - 1][j - 1];
        return dfs(1, 1, n, n);
    }

    Node* dfs(int x1, int y1, int x2, int y2) {
        int n = x2 - x1 + 1;
        int sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
        if (sum == 0 || sum == n * n) return new Node(!!sum, true);
        auto node = new Node(0, false);
        int m = n / 2;
        node->topLeft = dfs(x1, y1, x1 + m - 1, y1 + m - 1);
        node->topRight = dfs(x1, y1 + m, x1 + m - 1, y2);
        node->bottomLeft = dfs(x1 + m, y1, x2, y1 + m - 1);
        node->bottomRight = dfs(x1 + m, y1 + m, x2, y2);
        return node;
    }
};

class Solution {
public:
    int characterReplacement(string s, int k) {
        int res = 0;
        for (char c = 'A'; c <= 'Z'; c ++ ) {
            for (int i = 0, j = 0, cnt = 0; i < s.size(); i ++ ) {
                if (s[i] == c) cnt ++ ;
                while (i - j + 1 - cnt > k) {
                    if (s[j] == c) cnt -- ;
                    j ++ ;
                }
                res = max(res, i - j + 1);
            }
        }
        return res;
    }
};