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

**Definitions:**

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

9 10 11 12 13 14 15 16 17 18 |
# Works as a stack where ( pushes an element, and ) pops one for k in xrange(N): if S[k] == '(': size += 1 else: size -= 1 # If it try to pop an empty stack, error. if size < 0: return 0 |

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

20 21 22 23 24 |
# If the stack is empty at the end of processing the string, string is properly nested if size == 0: return 1 else: return 0 |

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:**

12345678910111213141516171819202122232425
# Name: Nesting# Link: https://codility.com/demo/take-sample-test/nesting/ def solution(S): N = len(S) size = 0 # Works as a stack where ( pushes an element, and ) pops one for k in xrange(N): if S[k] == '(': size += 1 else: size -= 1 # If it try to pop an empty stack, error. if size < 0: return 0 # If the stack is empty at the end of processing the string, string is properly nested if size == 0: return 1 else: return 0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
# Name: Nesting # Link: https://codility.com/demo/take-sample-test/nesting/ def solution(S): N = len(S) size = 0 # Works as a stack where ( pushes an element, and ) pops one for k in xrange(N): if S[k] == '(': size += 1 else: size -= 1 # If it try to pop an empty stack, error. if size < 0: return 0 # If the stack is empty at the end of processing the string, string is properly nested if size == 0: return 1 else: return 0 |

*Time Complexity O(N)*

*Space Complexity O(1)*

## One thought on “Codility – Nesting”