LSTR - Editorial

Difficulty level: Medium

Pre-requisites: Stack, basic programming concepts

Problem link:

Contest problem link

Practice problem link


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.


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