×

String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding

Miscellaneous

Nesting Depth - Google CodeJam 2020 qualification round problem solution

Here, we are going to find the solution of Nesting Depth - Google CodeJam 2020 qualification round problem with explanation and code.
Submitted by Radib Kar, on June 19, 2020

Problem statement

Given a string of digits S, insert a minimum number of opening and closing parentheses into it such that the resulting string is balanced and each digit d is inside exactly d pairs of matching parentheses.

Let the nesting of two parentheses within a string be the substring that occurs strictly between them. An opening parenthesis and a closing parenthesis that is further to its right are said to match if their nesting is empty, or if every parenthesis in their nesting matches with another parenthesis in their nesting. The nesting depth of a position p is the number of pairs of matching parentheses m such that p is included in the nesting of m

For example, in the following strings, all digits match their nesting depth: 0((2)1), (((3))1(2)), ((((4)))), ((2))((2))(1). The first three strings have minimum length among those that have the same digits in the same order, but the last one does not since ((22)1) also has the digits 221 and is shorter.

Given a string of digits S, find another string S', comprised of parentheses and digits, such that,

  • all parentheses in S' match some other parenthesis,
  • removing any and all parentheses from S' results in S,
  • each digit in S' is equal to its nesting depth, and
  • S' is of minimum length.

Input

The first line of the input gives the number of test cases, T. T lines follow. Each line represents a test case and contains only the string S.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the string S' defined above.

Constraints:

1 ≤ T ≤ 100.
1 ≤ length of S ≤ 100.
Each character in S is a decimal digit between 0 and 9, inclusive.

Example

Input:
4
0000
101
111000
1

Output:
Case #1: 0000
Case #2: (1)0(1)
Case #3: (111)000
Case #4: (1)

Explanation

The strings ()0000(), (1)0(((()))1) and (1)(11)000 are not valid solutions to Sample Cases #1, #2 and #3, respectively, only because they are not of minimum length. In addition, 1)( and )(1 are not valid solutions to Sample Case #4 because they contain unmatched parentheses and the nesting depth is 0 at the position where there is a 1.

You can create sample inputs that are valid only for Test Set 2 by removing the parentheses from the example strings mentioned in the problem statement.

Source: Qualification Round 2020 - Code Jam 2020 - Nesting Depth

Solution

Few points to note:

  1. Number of the opening bracket for digit I is i and number of opening brackets will be counted from the beginning and each closing bracket cancels out each opening bracket
    For example:
    ((2(3))) is valid and as 3 have three opening brackets before it and there's no closing bracket to cancel.
  2. What if a digit is less than the previous digit? We can balance by adding closing brackets as necessary to cancel the extra opening brackets out
    Continuing the above example:
    For 231
    We place 1 after the two closing brackets like below:
    ((2(3))1

Let the input string be str
Let's take the above example, so str="231"
Now let's give a detailed algo based on the above discussion

  1. The result string is initially initialized as empty ""
  2. Initially add as many opening brackets as needed as per value of str[0] and then put str[0]
    So as per our example str[0]=2 and thus two opening brackets will be added and then 2
    So result="((2" as of now
  3. For the other indexes i=1 to n-1
    If(str[i-1]==str[i])
        Simply add the digit
    Else if (str[i-1]<str[i])
        Add (str[i]-str[i-1]) number of opening brackets to balance 
        ( str[i]now have str[i]number of opening brackets before it)
    Else ##Str[i]<str[i-1]
        Add (Str[i-1]-str[i])number of closing brackets to balance 
        (str[i] now have str[i] number of opening brackets before 
        it as extra opening brackets are cancelled
    Finally put str[i]#the digit itself
    
  4. Finally put s[n-1] number of closing brackets to end the string,
    So, str[1]=3 and that's greater than 2. 
    We need (3-2) number of opening brackets
    
    So result ="((2(3"
    
    str[2]=1 and that's less than 3. 
    We need (3-1) number of closing brackets to balance
    
    So result ="((2(3))1"
    
    Finally put 1 closing bracket to end the string
    So final result is "((2(3))1)"
    

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int main()
{

    map<char, int> mymap;
    
    mymap['0'] = 0;
    mymap['1'] = 1;
    mymap['2'] = 2;
    mymap['3'] = 3;
    mymap['4'] = 4;
    mymap['5'] = 5;
    mymap['6'] = 6;
    mymap['7'] = 7;
    mymap['8'] = 8;
    mymap['9'] = 9;
    
    int t;
    cin >> t;
    
    for (int test_case = 1; test_case <= t; test_case++) {
        string s;
        cin >> s;
        string result = "";
        int n = s.length();
        for (int i = 0; i < s.length(); i++) {
            if (i == 0) {
                for (int j = 0; j < mymap[s[i]]; j++) {
                    result += string(1, '(');
                }
                result += string(1, s[i]);
            }
            else {
                if (s[i] == s[i - 1]) {
                    result += string(1, s[i]);
                }
                else if (s[i] < s[i - 1]) {
                    int num = mymap[s[i - 1]] - mymap[s[i]];
                    for (int j = 0; j < num; j++)
                        result += string(1, ')');
                    result += string(1, s[i]);
                }
                else {
                    int num = mymap[s[i]] - mymap[s[i - 1]];
                    for (int j = 0; j < num; j++)
                        result += string(1, '(');
                    result += string(1, s[i]);
                }
            }
        }
        for (int j = 0; j < mymap[s[n - 1]]; j++)
            result += string(1, ')');

        cout << "Case #" << test_case << ": " << result << endl;
    }

    return 0;
}

Output

3
231
Case #1: ((2(3))1)
321
Case #2: (((3)2)1)
123
Case #3: (1(2(3)))


Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.