Leetcode Problem:

• Create Binary Tree From Descriptions

Summary

• Constructing a binary tree from given descriptions of parent-child relationships.

Approach

• We use a map to store the nodes of the binary tree, where the key is the node value and the value is a pointer to the node
• We also use another map to store the parent of each node
• We iterate through the descriptions and create the nodes and their children accordingly
• Finally, we find the root of the tree by following the parent map until we reach a node that has no parent.

Complexity

• O(n), where n is the number of descriptions, because we make a single pass through the descriptions to create the nodes and their children.

Explain

• The solution starts by creating two maps: `myMap` to store the nodes and `parentMap` to store the parent of each node
• We then iterate through the descriptions and create the nodes and their children accordingly
• If a node does not exist in `myMap`, we create it
• We then set the left or right child of the parent node based on the value of `isLeft`
• Finally, we find the root of the tree by following the parent map until we reach a node that has no parent
• The time complexity is O(n) because we make a single pass through the descriptions to create the nodes and their children.

Solution Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* createBinaryTree(vector>& descriptions) {
        map myMap;
        map parentMap;
        int root = descriptions[0][0];
        for(int i = 0 ; i < descriptions.size(); i++){
            int parent = descriptions[i][0];
            int child = descriptions[i][1];
            int isLeft = descriptions[i][2];
            parentMap[child] = parent;
            if (myMap.find(parent) == myMap.end()){
                myMap[parent] = new TreeNode(parent);
            }
            if (myMap.find(child) == myMap.end()){
                myMap[child] = new TreeNode(child);
            }
            if (isLeft == 1){
                myMap[parent]->left = myMap[child];
            } else {
                myMap[parent]->right = myMap[child];
            }
        }
        while(parentMap.find(root) != parentMap.end()){
            root = parentMap[root];
        }
        return myMap[root];
    }
};

Leetcode Problem:

• Maximum Score From Removing Substrings

Summary

• Given a string s and two integers x and y, find the maximum points that can be gained by removing substrings of 'ab' and 'ba' from s.

Approach

• The solution uses a two-step approach
• First, it removes all occurrences of 'ab' or 'ba' from the string s, depending on which one has a higher value
• Then, it removes the remaining 'ab' or 'ba' substrings from the resulting string
• The points gained for each step are added to the total score.

Complexity

• O(n), where n is the length of the string s
• This is because the solution makes two passes through the string s, one for each step.

Explain

• The solution starts by initializing two vectors, firstStep and secondStep, to store the characters of the string s after the first and second steps, respectively
• It also initializes the total score res to 0
• The solution then iterates over the string s, adding characters to firstStep and secondStep based on whether they are 'ab' or 'ba'
• If a character is 'ab' or 'ba', the solution checks if the last character in the vector is the same as the character in 'ab' or 'ba'
• If they are the same, the solution adds the points gained for the step to the total score and removes the character from the vector
• Otherwise, the solution adds the character to the vector
• Finally, the solution returns the total score.

Solution Code:

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        int res = 0;
        vector firstStep;
        string cmpStr;
        int maxScore = max(x, y);
        int minScore = min(x, y);
        if (x > y){
            cmpStr = "ab";
        } else {
            cmpStr = "ba";
        }

        for(int i = 0 ; i < s.size(); i++){
            if (firstStep.size() == 0 || s[i] != cmpStr[1]){
                firstStep.push_back(s[i]);
            } else {
                char c = firstStep.back();
                if (c == cmpStr[0]){
                    res += maxScore;
                    firstStep.pop_back();
                } else {
                    firstStep.push_back(s[i]);
                }
            }
        }
        vector secondStep;

        for(int i = 0 ; i < firstStep.size(); i++){
            if (secondStep.size() == 0 || firstStep[i] != cmpStr[0]){
                secondStep.push_back(firstStep[i]);
            } else {
                char c = secondStep.back();
                if (c == cmpStr[1]){
                    res += minScore;
                    secondStep.pop_back();
                }else {
                    secondStep.push_back(firstStep[i]);
                }
            }
        }
        return res;
    }
};

summary

• Given a string s that consists of lower case English letters and brackets, reverse the strings in each pair of matching parentheses, starting from the innermost one.

approach

• This solution uses a stack to keep track of the indices of the characters that need to be reversed
• When a closing parenthesis is encountered, the solution pops the corresponding opening parenthesis index from the stack, reverses the substring between these two indices, and then removes the opening parenthesis from the stack.

complexity

• O(N)

explain

• The solution iterates over the string s
• When it encounters an opening parenthesis, it pushes the current length of the string onto the stack
• When it encounters a closing parenthesis, it pops the corresponding opening parenthesis index from the stack, reverses the substring between these two indices, and then removes the opening parenthesis from the stack
• The solution continues this process until it has processed the entire string.

Solution Code:

class Solution {
public:
    
    string reverseParentheses(string s) {
        string res = "";
        int mystack[2001];
        int stackIdx = 0;
        int N = s.length();
        int idx = 0;
        for(int i = 0 ; i < N; i++){
            if (s[i] == '('){
                mystack[stackIdx++] = res.length();
            } else if (s[i] == ')'){
                int popIdx = mystack[--stackIdx];
                reverse(res.begin()+popIdx, res.end());
            } else {
                res += s[i];
            }
        }
        return res;
    }
};