Google codejam 2020 solution to nesting depth problem

0 / 211
Nesting depth problem

Problem

 

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, TT 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.

 

 

Limits

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ length of S ≤ 100.

 

Test set 1 (Visible Verdict)

 

Each character in S is either 0 or 1.

 

 

Test set 2 (Visible Verdict)

 

Each character in S is a decimal digit between 0 and 9, inclusive.

 

 

Sample

 

Input
 
Output
 
4
0000
101
111000
1

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

  

 

 

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.

 

Solution below using C++

 

#include <bits/stdc++.h>


using namespace std;


int main() {
  int T, k = 1;
  

  cin >> T;
  cin.ignore();

  while (T--) {
    string str;
	getline(cin,str);
	// do string maniulation for parantheses
	int leftParenCount = 0;
	std::string output = "";
	
	for (int i = 0; i < str.length(); i++) {
	    int digit = str[i] - 0x30;
	    
	    int bound = abs(digit-leftParenCount);
	    
	    for (int j = 1; j <= bound ; j++) {
	        if (digit-leftParenCount < 0) {
	            output += ")";
	            leftParenCount--;
	        }
	        else {
	            output += "(";
	            leftParenCount++;
	        }
	    }
	    output += str[i];
	}
	
	for (int t = 1; t <= leftParenCount; t++) {
	    output += ")";
	}

    cout << "Case #" << k << ": " << output << endl;
    
    //k is for printing the Case Number
    k++;
  }

  return 0;
}

 

 

Explanation

 

  • Initialize leftParenCount = 0 which keeps track of the left/right parentheses

 

  • Iterate through the string, get digit numeric value of each character

 

  • During each iteration, calculate the difference between the current digit and leftParenCount, if that’s negative,  append those many “)” if it’s positive we append those many “(“.

 

  • For each closing parentheses appended “)”, decrement the leftParenCount by 1 and for each opening parentheses appended increment it’s value by 1.

 

  • Append the digit after the parentheses.

 

  • After the entire string is iterated through, append N closing parentheses to close the string where N = 1 to leftParenCount.

 

The algorithm is pretty straightforward and easy to follow and runs in O(n) time.

 

Subscribe and follow Golibrary on Facebook and Linkedin to get all the updates.

 

 

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.

Related Posts