class TrieNode {
public:
    unordered_map<char, TrieNode*> mapping;
    bool endFlag;
    TrieNode() {
        endFlag = false;
    }
};

class MagicDictionary {
private:
  TrieNode* root;  
public:
    /** Initialize your data structure here. */
    MagicDictionary() {
        root = new TrieNode();
    }
    
    /** Build a dictionary through a list of words */
    void buildDict(vector<string> dict) {
        for (auto& item: dict) {
            TrieNode* traverse = root;
            for (int i = 0; i < item.size(); ++i) {
                auto iter = traverse->mapping.find(item[i]);
                if (iter == traverse->mapping.end()) traverse->mapping[item[i]] = new TrieNode();
                traverse = traverse->mapping[item[i]];
            }
            traverse->endFlag = true;
        }
        
        return;
    }
    
    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    bool search(string word) {
        bool success = false;
        helper(false, root, 0, word, success);
        return success;
    }
    
    void helper(bool tag, TrieNode* cur, int index, string& word, bool& success) {
        if (index == word.size()) {
            if (tag == true && cur->endFlag == true) success = true;
            return;
        }
            
        for (auto& item : cur->mapping) {
            if (item.first != word[index] && tag == false) {
                helper(true, item.second, index + 1, word, success);
            }
            if (item.first == word[index]) {
                helper(tag, item.second, index + 1, word, success);
            }
        }
        
        return;
    }
};

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary obj = new MagicDictionary();
 * obj.buildDict(dict);
 * bool param_2 = obj.search(word);
 */

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        unordered_map<int, int> mapping;
        if (root == NULL || (root->left ==NULL && root->right == NULL)) return false;
        bool ret = false;
        helper(mapping, root, k, ret);
        return ret;
    }
    
    void helper(unordered_map<int, int>& mapping, TreeNode* root, int k, bool& ret) {
        if (ret || root == NULL) return;
        if (mapping.count(k - root->val) != 0) {ret = true; return;}
        mapping[root->val] = 1;
        helper(mapping, root->right, k, ret);
        helper(mapping, root->left, k , ret);
        return;
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret;
        if (nums.size() < 2) return ret;
        unordered_map<int, int> mapping;
        for (int i = 0; i < nums.size(); ++i) mapping[nums[i]] = i;
        for (int i = 0; i < nums.size(); ++i) {
            if(mapping.count(target - nums[i]) == 0 || mapping[target - nums[i]] == i) continue;
            ret.push_back(i);
            ret.push_back(mapping[target - nums[i]]);
            return ret;
        }
        return ret;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int countUnivalSubtrees(TreeNode* root) {
        int count = 0;
        if (root == NULL) return 0;
        helper(count, root);
        return count;
    }
    
    int helper(int& count, TreeNode* root) {
        
        int leftValue = (root->left) ? helper(count, root->left) : INT_MIN;
        int rightValue = (root->right) ? helper(count, root->right) : INT_MIN;
        
        if (leftValue == INT_MAX || rightValue == INT_MAX) return INT_MAX;
        
        if ( (leftValue == INT_MIN || root->val == leftValue) &&
            (rightValue == INT_MIN || root->val == rightValue) ) {
            count += 1;
            return root->val;
        }
        
        //Failed
        return INT_MAX;
    }
};

class MovingAverage {
private:
    int currentSize;
    queue<int> q;
    double sum;
    int maxSize;
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        maxSize = size;
        sum = 0;
        currentSize = 0;
    }
    
    double next(int val) {
        q.push(val);
        sum += val;
        if (q.size() > maxSize) {
            sum -= q.front();
            q.pop();
        }
        
        return sum / q.size();
    }
};

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

class MaxStack {
private:
    map<int, stack<list<int>::iterator> > mapping;
    list<int> lis;
public:
    /** initialize your data structure here. */
    MaxStack() {
        
    }
    
    void push(int x) {
        lis.push_front(x);
        mapping[x].push(lis.begin());
    }
    
    int pop() {
        int ret = lis.front();
        mapping[ret].pop();
        if (mapping[ret].empty()) mapping.erase(ret);
        lis.pop_front();
        return ret;
    }
    
    int top() {
        return lis.front();
    }
    
    int peekMax() {
        return mapping.rbegin()->first;
    }
    
    int popMax() {
        auto iter = mapping.rbegin()->second.top();
        int ret = *iter;
        mapping.rbegin()->second.pop();
        if (mapping.rbegin()->second.empty()) 
            mapping.erase(ret);
        lis.erase(iter);
        return ret;
    }
};

/**
 * Your MaxStack object will be instantiated and called as such:
 * MaxStack obj = new MaxStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.peekMax();
 * int param_5 = obj.popMax();
 */

class Solution {
public:
    int minCostII(vector<vector<int>>& costs) {
        int size = costs.size();
        if (size == 0) return 0;
        int colorNumber = costs[0].size();
        
        vector<vector<int>> dp(size + 1, vector<int>(colorNumber, 0));
        pair<int, int> minCost;
        minCost.second = 0;
        minCost.first = -1;
        pair<int, int> secondMinCost;
        secondMinCost.second = 0;
        secondMinCost.first = -1;
        for (int i = 1; i <= size; ++i) {
            int targetIndex = -1;
            int targetCost = INT_MAX;
            int secondIndex = -1;
            int secondCost = INT_MAX;
            for (int j = 0; j < colorNumber; ++j) {
                dp[i][j] = costs[i - 1][j] + 
                    (minCost.first == j ? secondMinCost.second : minCost.second);
                if (dp[i][j] < targetCost) {
                    secondIndex = targetIndex;
                    secondCost = targetCost;
                    targetCost = dp[i][j];
                    targetIndex = j;
                }else if (dp[i][j] < secondCost) {
                    secondIndex = j;
                    secondCost = dp[i][j];
                }
            } 
            minCost.first = targetIndex;
            minCost.second = targetCost;
            secondMinCost.first = secondIndex;
            secondMinCost.second = secondCost;
        }
        
        return minCost.second;
    }
};

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int size = costs.size();
        if (size == 0) return 0;
        vector<vector<int>> dp(size + 1, vector<int>(3, 0));
        
        for (int i = 1; i <= size; ++i) {
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
        }
        
        return min(min(dp[size][0], dp[size][1]), dp[size][2]);
    }
};

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int maxLens = 0;
        int curLens = 0;
        unordered_map<char, int> counter;
        int preIndex = 0;
        for (int i = 0; i < s.size(); ++i) {
            counter[s[i]] += 1;
            while (counter.size() > 2) {
                counter[s[preIndex]] -= 1;
                if (counter[s[preIndex]] == 0) counter.erase(s[preIndex]);
                preIndex += 1;
                curLens -= 1;
            }
            curLens += 1;
            maxLens = max(maxLens, curLens);
        }
        return maxLens;
    }
};

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        return helper(n, 0);
    }
    
    vector<string> helper(int n, int depth) {
        vector<string> ret;
        if (n < 0) return ret;
        if (n == 0) {
            ret.push_back("");
            return ret;
        }
        if (n == 1) {
            ret.push_back("1");ret.push_back("8");ret.push_back("0");
            return ret;
        }
        
        auto base = helper(n - 2, depth + 1);
        for (auto& item : base) {
            ret.push_back('6' + item + '9');
            ret.push_back('9' + item + '6');
            ret.push_back('1' + item + '1');
            ret.push_back('8' + item + '8');
            if (depth != 0) ret.push_back('0' + item + '0');
        }
        
        return ret;
    }

};