Nesting at app.codility.com/programmers in C++ Explained: Determine whether a given string of parentheses (single type) is properly nested.
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N)
Lesson 7 at app.codility.com/programmers
The solution and its explanation are given below.
Category of Article : Technology | Computers and Software | Algorithm
By: Chrysanthus Date Published: 4 Jul 2025
Problem
A string S consisting of N characters is called properly nested if:
• S is empty;
• S has the form "(U)" where U is a properly nested string;
• S has the form "VW" where V and W are properly nested strings.
For example, string "(()(())())" is properly nested but string "())" isn't.
Write a function:
int solution(string &S);
that, given a string S consisting of N characters, returns 1 if string S is properly nested and 0 otherwise.
For example, given S = "(()(())())", the function should return 1 and given S = "())", the function should return 0, as explained above.
Write an efficient algorithm for the following assumptions:
• N is an integer within the range [0..1,000,000];
• string S is made only of the characters '(' and/or ')'.
Note:
There is only one type of brackets, which is ( open with ) close.The issue with algorithm problems is not just to produce a working solution function, but it is to produce a working (correct) solution that is efficient (performance).
The properly nested pair is: () . Each open bracket on the left must have a close bracket on the right, not necessarily consecutively. No group or subgroup of pairs can start with a close bracket. The total number of brackets must be even.
Let V = "()"
Let W = "(())"
Then S = "(VWV)" = "(()(())())"
This is a properly nested string consisting of three subgroups, with two being the same, as V. The three subgroups are within "()" to form the complete group. Note that at the center of each subgroup is an open and close bracket. Immediately on the left and right can be, another open and close brackets. This continues outwards until a subgroup is formed.
Strategy
Do not forget that an empty string is a properly nested string. So the first thing to do, is to check if the string is empty. If it is, return 1 and the algorithm stops.A string or substring should not begin with a close bracket. If that is the case, return 0 and the algorithm stops. Otherwise begin to push the open brackets on the left into a stack. When a closing bracket is encountered, it must be closing the last bracket pushed to the stack (center of subgroup). If that is not the case, then return 0 and algorithm stops. If that is the case, then (so far so good) the last bracket in the stack and the bracket coming in, form a properly nested pair. In that case, remove the last bracket in the stack and do not push the in-coming bracket to the stack. The stack loses one bracket at the top. Note that a closing bracket followed by its opening bracket, i.e. )( , does not form a properly nested pair.
This continues until all the brackets in the given string have been accessed. If the stack is not empty at this time, then not all the opening brackets were closed. In that case, return 0 (not properly nested).
Solution in O(N) Time
A program with the solution function is (read through the code):#include <iostream>The output is:
#include <string>
#include <stack>
using namespace std;
int solution(string &S) {
int N = S.size();
stack<char> stk;
if (N == 0)
return 1;
for (int i=0; i<N; ++i) {
char c = S[i];
if (c == '(')
stk.push(c);
else if (c == ')' && stk.size() != 0)
stk.pop();
else
return 0;
}
if (stk.size() > 0)
return 0;
return 1;
}
int main(int argc, char **argv)
{
string P = string("(()(())())");
int ret1 = solution(P);
cout << ret1 << endl;
string Q = string("())");
int ret2 = solution(Q);
cout << ret2 << endl;
return 0;
}
1
0
Note the condition, &&(stk.size != 0) in the overall else-if condition. That condition can easily be omitted (forgotten). Also appreciate the difference between the use of || and && . The last "return 1" in the solution() function, means no abnormality was detected.
At app.codility.com/programmers the scoring and detected time complexity for this solution() is:
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N)
Thanks for reading.