Leetcode Weekly Contest 144

1108. Defanging an IP Address

Problem

• Input: "1.1.1.1" Output: "1[.]1[.]1[.]1"

• Input: "255.100.50.0" Output: "255[.]100[.]50[.]0"

Approach

• Traverse the string.

• For each character:
• If it is ., append [.] to the result.
• Else, append the character itself.

Code

class Solution {
public:
    string defangIPaddr(string address) {
        string res = "";
        for(char &ch: address){
            if(ch == '.') res += "[.]";
            else res += ch;
        }
        return res;
    }
};

1109. Corporate Flight Bookings

Problem

• Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]

Approach

• Use a difference array:
• Add seats at start-1.
• Subtract seats at end (if end < n).

• Compute prefix sum to get actual seats for each flight.

Code

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> seats(n, 0);
        for(auto &b: bookings){
            int start = b[0], end = b[1], seat = b[2];
            seats[start-1] += seat;
            if(end < n) seats[end] -= seat;
        }
        for(int i = 1; i < n; i++) seats[i] += seats[i-1];
        return seats;
    }
};

1110. Delete Nodes And Return Forest

Problem

• Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

Approach

• Use BFS/DFS traversal.

• Track nodes to delete using a set or array.

• If a node is deleted:
• Detach it from parent.
• Its children (if not deleted) become new roots.

• Collect all new roots in a result vector.

Code

class Solution {
public:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        vector<TreeNode*> res;
        if(!root) return res;

        vector<int> st(10001, 0);
        for(int &val: to_delete) st[val] = 1;

        queue<pair<TreeNode*, bool>> q;
        q.push({root, false});
        unordered_map<TreeNode*, TreeNode*> parentMap;

        while(!q.empty()){
            TreeNode* cur = q.front().first;
            bool status = q.front().second;
            q.pop();

            if(st[cur->val]){
                TreeNode* parent = parentMap[cur];
                if(parent){
                    if(parent->left == cur) parent->left = nullptr;
                    if(parent->right == cur) parent->right = nullptr;
                }
                if(cur->left) q.push({cur->left, false});
                if(cur->right) q.push({cur->right, false});
            }
            else {
                if(!status) res.push_back(cur);
                if(cur->left){
                    q.push({cur->left, true});
                    parentMap[cur->left] = cur;
                }
                if(cur->right){
                    q.push({cur->right, true});
                    parentMap[cur->right] = cur;
                }
            }
        }
        return res;
    }
};

1111. Maximum Nesting Depth of Two Valid Parentheses Strings

Problem

• Input: "(()())" → Output: [0,1,1,1,1,0]

Approach

• Use a stack or depth counter:
• Keep track of nesting depth.
• Alternate assignment of '(' and ')' to A and B to minimize max depth.

Code

class Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {
        int n = seq.size();
        stack<char> st1, st2;
        vector<int> res(n);
        for(int i = 0; i < n; i++){
            char ch = seq[i];
            if(ch == '('){
                if(st2.size() < st1.size()){
                    st2.push('(');
                    res[i] = 1;
                } else {
                    st1.push('(');
                    res[i] = 0;
                }
            } else {
                if(st2.size() < st1.size()){
                    st1.pop();
                    res[i] = 0;
                } else {
                    st2.pop();
                    res[i] = 1;
                }
            }
        }
        return res;
    }
};