Difficulty level: Medium
Pre-requisites: Stack, basic programming concepts
Problem link:
Problem:
Given a of strings, find the number of strings which satisfy the following properties:
- If there is an arch drawn from each
character to the next occurrence of
the same character, the arches should
not intersect. - All the characters should be on
one end of an arch.
Explanation:
This problem is a simple implementation of stack. Consider an empty stack. For each character of the string ,C push C to the stack if the stack is empty of the character on top of the stack is not equal to ch. If character C mathces the character on top of the string, then pop it.
If the stack is empty after the operation is over, the string satisfies the properties. Increment a counter.
Problem setter’s solution: SOLUTION