GFG PROBLEM OF THE DAY - SOLUTIONS

 7 MAY

GENERATING PARENTHESES

Given an integer N representing the number of pairs of parentheses, the task is to generate all combinations of well-formed(balanced) parentheses.

REFER-1 

REFER-2

 void addParenthesis(vector<string>& v, string str, int left, int right){

        if(left == 0 && right == 0){

            v.push_back(str);

            return;

        }

        if(right > 0)

            addParenthesis(v, str+")", left, right-1);

        if(left > 0)

            addParenthesis(v, str+"(", left-1, right+1);

    } 

    vector<string> AllParenthesis(int n) 

    {

        vector<string>res;

        

        if(n > 0){

            addParenthesis(res,"", n, 0);

        }

        return res;    

    }

8 MAY 

FLATTENING A LINKED LIST

Given a Linked List of size N, where every node represents a sub-linked-list and contains two pointers:
(i) a next pointer to the next node,
(ii) a bottom pointer to a linked list where this node is head.
Each of the sub-linked-list is in sorted order.
Flatten the Link List such that all the nodes appear in a single level while maintaining the sorted order. 

REFER

Node* merge(Node *a, Node *b){

    if(a == NULL)

        return b;

    if(b == NULL)

        return a;

    Node *res;

    if(a->data < b->data){

        res = a;

        res->bottom = merge(a->bottom, b);

    }

    else{

        res = b;

        res->bottom = merge(a, b->bottom);

    }

    res->next = NULL;

    return res;

}

Node *flatten(Node *root)

{

    if(root == NULL || root->next == NULL)

        return root;

    return merge(root, flatten(root->next));

}

9 MAY 

REMOVE K DIGITS

Given a non-negative integer S represented as a string, remove K digits from the number so that the new number is the smallest possible.

REFER

void buildLowestRec(string S, int K, string& res){

        if(K == 0){

            res.append(S);

            return;

        }

        int len = S.length();

        if(len <= K){

            return;

        }

        int minIndex = 0;

        for(int i = 1; i <= K; i++){

            if(S[i] < S[minIndex])

                minIndex = i;

        }

        res.push_back(S[minIndex]);

        string new_str = S.substr(minIndex+1, len-minIndex);

        buildLowestRec(new_str, K-minIndex, res);

    }

    string removeKdigits(string S, int K) {

        string res = "";

        buildLowestRec(S, K, res);

        string ans = "";

        int flag = 0;

        for(int i = 0; i < res.length(); i++){

            if(res[i] != '0' || flag == 1){

                flag = 1;

                ans += res[i];

            }

        }

        if(ans.length() == 0)

            return "0";

        else 

            return ans;

    }