Codility - Nesting

Solution to Codility lesson5-exercise1 Nesting problem, link to Codility problem and complete solution at the end of the post.

Definitions:
\{N \in \mathbb{N}\ |\ 0\leq N \leq 1,000,000\}

Properly nested string S:

  • 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.

Problem:
Define a function solution with input S , such that solution returns 1 if string S is properly nested and 0 otherwise.

  • Expected worst-case time complexity is O(N);
  • Expected worst-case space complexity is O(1).

Analysis:

To solve this we will simulate how a stack works, but instead of storing the elements, we are only going to track the stack size.
The main loop will iterate through the chars of S. And if char is "(" we push, and if char is ")" we pop. If the size goes below zero we have a non properly nested string, because the string now could be represented by U).... where U is a properly nested string and there is no pair for the ")" char.

After iterating through S, if the size of the stack is greater than 0, S is not properly nested. Because S is of the form U((((... with U being properly nested.

This problem is also part of the Computer Theory field and what we did can also be done with a PDA.
Visiting every element of S gives us a time complexity of O(N).
For the space complexity we have O(1).

Complete Solution:

Time Complexity O(N)
Space Complexity O(1)

Link to GitHub solution here .
Link to Codility problem here .

One thought on “Codility - Nesting

/*Comment here*/