SDE - Intern

It’s christmas and Santa is here with ‘K’ gifts. There are ‘N’ children in the park who are standing in a straight line, and not crowding up due to COVID restrictions. You are given an array “distance” containing ‘N’ integers where “distance[i]” denotes the distance of the ith child from the gate of the park in meters. Each child stands at a different distance from the gate.

Since Santa is still on his reindeer, he can land at any position in the park. But once he lands on the ground, he uses his feet to walk. Santa is very lazy and is requesting you to find the minimum distance he needs to travel on his feet so that he can distribute all the ‘K’ gifts to ‘K’ different children.

Example:

Let there be 6 children and 3 gifts. If the position of the children is [3, 6, 7, 10, 17, 25], the minimum distance Santa has to walk is 4m which can be achieved in many ways, one of them being Santa landing at the 1st child and walking till the 3rd child (distance = (6m - 3m) + (7m - 6m) = 4m).

You have been given a string 'S' containing only three types of characters, i.e. '(', ')' and '*'.

A Valid String is defined as follows:

1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
5. An empty string is also valid.

Your task is to find out whether the given string is a Valid String or not.