Nesting Depth
Problem
tl;dr: 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.
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 Case #1: 0000
0000 Case #2: (1)0(1)
101 Case #3: (111)000
111000 Case #4: (1)
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.
Analysis
Test Set 1
To solve Test Set 1, we can put an opening parenthesis before each group of 1s and a closing parenthesis after.
We can use the following trick to simplify the implementation: prepend and append one extra 0 to S. Then the implementation is just replacing 01 with 0(1 and 10 with 1)0, which can be written in one line of code in some programming languages. Don't forget to remove the extra 0s from the end of the resulting string!
Test Set 2
For convenience, let's once again use the trick described above: prepend and append extra 0s to S, and then scan S from left to right.
Suppose we see some number A immediately followed by some larger number B and suppose all of the previously inserted parentheses would leave A at the right nesting depth — that is, there are exactly A unmatched opening parentheses preceding A, and no unmatched closing parentheses. For B to be at nesting depth B we need to add at least B - A opening parentheses. We can just do that and nothing else, to keep the final string length minimal. Any additional opening parentheses we would add would need to be closed before B, which would needlessly lengthen the string. Similarly, if we see some number A immediately followed by some smaller number B, we can just insert A - B closing parentheses. And in the case when A is equal to B, we don't need to add anything.
We don't need any parentheses before the temporary 0 in the beginning, or after the one in the end, so we can just drop them before printing the result.
Since we only add p parentheses when at least p are needed, the resulting string is of minimum length.
An inefficient but fun solution
The problem can be solved using only string replacements. First, replace each digit D with D (s, then the digit itself, then D )s. Then eliminate all instances of )(, collapsing the string each time, until there are no more to remove.
Here's a Python3 implementation:
for C in range(int(input())):
rawstr = ''.join([int(x) * '(' + x + ')' * int(x) for x in str(input())])
for _ in range(9):
rawstr = rawstr.replace(')(', '')
print("Case #{}: {}".format(C+1, rawstr))
Recommended: Please try your approach on your integrated development environment (IDE) first, before moving on to the solution.
Few words from CodingHumans : Don't Just copy paste the solution, try to analyze the problem and solve it without looking by taking the the solution as a hint or a reference . Your understanding of the solution matters.
HAVE A GOOD DAY 😁
Solution:
( java )
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Scanner;
public class NestingDepth {
private static final boolean DEBUG = true;
private static StringBuilder solve(String source) {
StringBuilder result = new StringBuilder();
int depth = 0;
for (int i = 0; i < source.length(); i++) {
char c = source.charAt(i);
int v = c - '0';
if (v < depth) {
for (int j = 0; j < depth - v; j++)
result.append(')');
} else if (v > depth) {
for (int j = 0; j < v - depth; j++)
result.append('(');
}
result.append(c);
depth = v;
}
if (depth > 0) {
for (int j = 0; j < depth; j++)
result.append(')');
}
return result;
}
