class Solution {
public:
    string removeDuplicateLetters(string s) {
        
        vector<char> st;
        vector<int> counter(26);
        vector<bool> visited(26);
        for (int i = 0; i < s.size(); ++i) 
            counter[s[i]-'a'] += 1;
        
        for (int i = 0; i < s.size(); ++i) {
            --counter[s[i]-'a'];
             if (visited[s[i]-'a']) continue;
            while (!st.empty() && st.back() > s[i] 
                && counter[st.back()-'a'] > 0) {
                visited[st.back()-'a'] = false;
                st.pop_back();
            }
            st.push_back(s[i]);
            visited[st.back()-'a'] = true;
        }
        
        return string(st.begin(), st.end());
    }
    
    
};

/**
 * 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:
    vector<int> boundaryOfBinaryTree(TreeNode* root) {
        vector<int> ret;
        if (!root) return ret;
        ret.push_back(root->val);
        if (!root->left && !root->right) return ret;
        
        TreeNode* traverseLeft = root->left;
        while(traverseLeft && (traverseLeft->left || traverseLeft->right) ) {
            ret.push_back(traverseLeft->val);
            traverseLeft = traverseLeft->left 
                ? traverseLeft->left : traverseLeft->right;
        }
        
        //Traverse all the left node
        traverseLeaf(ret, root);
        
        stack<int> st;
        TreeNode* traverseRight = root->right;
        //stack to store the right handside non-leaf node
        while (traverseRight && (traverseRight->right || traverseRight->left) ) {
            st.push(traverseRight->val);
            traverseRight = traverseRight->right 
                ? traverseRight->right : traverseRight->left;
        }
        
        while(!st.empty()) {
            ret.push_back(st.top());
            st.pop();
        }
        
        return ret;
    }
    
    void traverseLeaf(vector<int>& ret, TreeNode* root) {
        if (root == NULL) return;
        if (root->left == NULL && root->right == NULL) ret.push_back(root->val);
        traverseLeaf(ret, root->left);
        traverseLeaf(ret, root->right);
        
        return;
    }
};

/**
 * 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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) return NULL;
        if ( (root->val <= p->val && root->val >= q->val) || 
             (root->val <= q->val && root->val >= p->val)) return root;
        
        if (root->val < p->val) return lowestCommonAncestor(root->right, p, q);
        return lowestCommonAncestor(root->left, p, q);
    }
    
};

class Solution {
public:
    vector<vector<int>> candyCrush(vector<vector<int>>& board) {
        int m = board.size();
        int n = board[0].size();
        
        while(true) {
            vector<pair<int, int>> del;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (board[i][j] == 0) continue;
                    int upper = i + 1, lower = i -1; 
                    int lefter = j - 1, righter = j + 1;
                    while(upper < m && upper - i < 3 
                      && board[upper][j] == board[i][j]) ++upper;
                    while(lower >= 0 && i - lower < 3
                      && board[lower][j] == board[i][j]) --lower;
                    while(righter < n && righter - j < 3
                      && board[i][righter] == board[i][j]) ++righter;
                    while(lefter >= 0 && j - lefter < 3
                      && board[i][lefter] == board[i][j]) --lefter;

                    if (righter -lefter > 3 || upper - lower > 3)
                        del.push_back(make_pair(i, j));
                }
            }
            if (del.size() == 0) break;
            
            for (auto& item:del) board[item.first][item.second] = 0;
            
            //Begin erasing....
            for (int j = 0; j < n; ++j) {
                vector<int> temp;
                for (int i = m - 1; i >= 0; --i) 
                    if(board[i][j] != 0)
                        temp.push_back(board[i][j]);
                
                int k = m - 1;
                int index = 0;
                while(index < temp.size()) {
                    board[k--][j] = temp[index++];
                }
                while(k >= 0) board[k--][j] = 0;
            }
        }
        return board;
    }
};

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

    Node() {}

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

    // Encodes a tree to a single string.
    string serialize(Node* root) {
        string ret;
        if (root == NULL) return ret;
        helperSerialize(root, ret);
        return ret;
    }
    
    void helperSerialize(Node* root, string& ret) {
        ret += to_string(root->val);
        if (root->children.size() == 0) return;
        ret += '[';
        for(auto& item : root->children) {
            helperSerialize(item, ret);
            ret += ' ';
        }   
        ret += ']';
        return;
    }
    
    int extractNumber(string& s, int& index, int size) {
        int ret = 0;
        while(index < size && (s[index] <= '9' && s[index] >= '0')) {
            ret *= 10;
            ret += (s[index] - '0');
            index += 1;
        }
        return ret;
    }
    
    // Decodes your encoded data to tree.
    Node* deserialize(string data) {
        Node* ret = NULL;
        int index = 0;
        int size = data.size();
        helperDeserialize(data, ret, index, size);
        return ret;
    }
    
    void helperDeserialize(string& data, Node*& root, int& index, int size) {
        if (index >= size) return;
        int val = extractNumber(data, index, size);
        root = new Node(val, vector<Node*>());
        
        if (index == size || data[index] != '[') return;
        index += 1; //Skip the '['
        
        while (index < size && data[index]!= ']') {
            root->children.push_back(NULL);
            helperDeserialize(data, root->children.back(), index, size);
            index += 1; //Skip the whitespace
        }
        index += 1; //Skip the ']'
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

class Solution {
public:
    vector<int> partitionLabels(string S) {
        vector<pair<int, int>> pairVector;
        vector<int> position(26, -1); //The mapping between character to interval index
        int index = 0;
        while (index < S.size()) {
            if(position[S[index]-'a'] == -1) {
                position[S[index]-'a'] = pairVector.size();
                pairVector.push_back(make_pair(index, index));
            } else {
                int startIndex = position[S[index]-'a']; //The starting index to merge
                pairVector[startIndex].second = index;
                if (startIndex < pairVector.size()-1) {
                    for (int i = pairVector[startIndex + 1].first; i <= pairVector[pairVector.size()-1].second; ++i) {
                        position[S[i]-'a'] = startIndex;
                    }
                }
                
                pairVector.resize(startIndex + 1);
            }
            ++index;
        }
        vector<int> ret;
        for (auto& item : pairVector) {
            cout << item.first << item.second << endl;
            ret.push_back(item.second - item.first + 1);
        }
        return ret;
    }
};

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int height = board.size();
        if (height == 0) return 0;
        int weight = board[0].size();
        int ret = 0;
        for (int i = 0; i < height; ++i) {
            for (int j = 0; j < weight; ++j) {
                if (board[i][j] == 'X' && 
                    (i + 1 == height || board[i + 1][j] == '.') && 
                    (j + 1 == weight || board[i][j + 1] == '.')) //Check if this is right down corner
                    ret += 1;
            }
        }
        return ret;
    }
};

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int sizeA = s1.size();
        int sizeB = s2.size();
        if (sizeA == 0) return true;
        unordered_map<char, int> counter;
        for (int i = 0; i < sizeA; ++i) {
            ++counter[s1[i]];
        }
        
        for (int i = 0; i < sizeB; ++i) {
            if (counter.find(s2[i]) != counter.end() && counter[s2[i]] > 0) {
                --counter[s2[i]];
                if (counter[s2[i]] == 0) counter.erase(s2[i]);
                if (counter.size() == 0) return true;
                if (helper(counter, s2, i + 1, sizeB)) return true;
                ++counter[s2[i]];
            }
        }
        return false;
    }
    
    bool helper(unordered_map<char, int> counter, string& s2, int index, int sizeB) {
        for (int i = index; i < sizeB; ++i) {
            if (counter.find(s2[i]) == counter.end() 
                    || counter[s2[i]] == 0) return false;
            if ((--counter[s2[i]]) == 0) counter.erase(s2[i]);
            if (counter.size() == 0) return true;
        }
        return false;
    }
};

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int sizeA = s1.size();
        int sizeB = s2.size();
        if (sizeA > sizeB) return false;
        vector<int> counter1(26), counter2(26);
        for(int i = 0; i < sizeA; ++i) {
            ++counter1[s1[i]-'a'];
            ++counter2[s2[i]-'a'];
        }
        
        if (counter1 == counter2) return true;
        
        for (int i = sizeA; i < sizeB; ++i) {
            ++counter2[s2[i]-'a'];
            --counter2[s2[i-sizeA]-'a'];
            if (counter1 == counter2) return true;
        }
        
        return false;
    }
};

#include <iostream>
#include <memory>

template<typename T>
class NaiveSmartPointer {
private:
    T* _ptr;
    size_t* _count;
public:
    NaiveSmartPointer(T* ptr = nullptr) : _ptr(ptr) {
        if (_ptr) {
            _count = new size_t(1);
        }else {
            _count = new size_t(0);
        }
    }
    
    NaiveSmartPointer(SmartPointer& ptr) {
        if (this != &ptr) {
            this->_ptr = ptr._ptr;
        	this->_count = ptr._count;
            ++(*this->_count);
        }
    }
    
    NaiveSmartPointer& operator=(const SmartPointer &ptr) {
        if (this->_ptr == ptr._ptr) return *this;
        
        if (this->_ptr) {
            --(*this->_count);
            if (*this->_count == 0) {
                //Recycle the pointed object;
                delete this->_ptr; 
                delete this->_count;
            }
        }
        
        this->_ptr = ptr._ptr;
        this->_count = ptr._count;
        ++(*this->_count);
        return *this;
    }
    
    T& operator*() {
        assert(this->_ptr == nullptr);
        return *(this->_ptr);
    }
    
    T* operator->() {
        assert(this->_ptr == nullptr);
        return this->_ptr;
    }
    
    ~SmartPointer () {
        --(*this->_count);
        if (*this->_count == 0) {
            delete this->_ptr;
            delete this->_count;
        }
    }
    
    size_t use_count() {
        return *this->_count;
    }
}

#include<memory>

class B;
class A {
public:
	std::shared_ptr<B> m_b;    	
}

class B {
public:
	std::shared_ptr<A> m_a;
}

int main() {
    while(true) {
        std::shared_ptr<A> a(new A); //Initialize A's reference count(1)
        std::shared_ptr<B> b(new B); //Initialize B's reference count(1)
        
        a->m_b = b; //Increase B's reference count(2)
        b->m_a = a; //Increase A's reference count(2)
    }
    //When the variable a and b are out of scope, we should decrease the reference count of targeted oject, so the final rc of A and B is 1, which will not recyle the space of object A and B.
}

template<typename T>
class unique_ptr {
private:
    T* _ptr;
public:
    unique_ptr(T& t) {
        _ptr = &t;
    }
    
    unique_ptr(unique_ptr<T>&& uptr) {
        _ptr = std::move(uptr._ptr);
        uptr._ptr = nullptr;
    }
    
    ~unique_ptr() {
       delete _ptr;
    }
    unique_ptr<T>& operator=(unique_ptr<T>&& uptr) {
       if (this == uptr) return *this;
       _ptr = std::move(uptr._ptr);
       uptr._ptr = nullptr;
       return *this;
    }
}

class PhoneDirectory {
public:
    unordered_map<int, list<int>::iterator > setting;
    list<int> lis;
    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    PhoneDirectory(int maxNumbers) {
        for (int i = 0; i < maxNumbers; ++i) {
            lis.push_back(i);
            setting[i] = lis.begin();
        }
    }
    
    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    int get() {
        if (lis.empty()) return -1;
        int ret = *(lis.begin());
        setting.erase(ret);
        lis.pop_front();
        return ret;
    }
    
    /** Check if a number is available or not. */
    bool check(int number) {
        return setting.find(number) != setting.end();
    }
    
    /** Recycle or release a number. */
    void release(int number) {
        if (setting.count(number) != 0) return;
        lis.push_front(number);
        setting[number] = lis.begin();
    }
};

/**
 * Your PhoneDirectory object will be instantiated and called as such:
 * PhoneDirectory obj = new PhoneDirectory(maxNumbers);
 * int param_1 = obj.get();
 * bool param_2 = obj.check(number);
 * obj.release(number);
 */