BANDPROC - Editorial

editorial
1

PROBLEM LINK:

Practice
Contest

Author: Yash Shah
Tester: Roshan Gupta, Shivam Sarang, Hrishikesh Patel
Editorialist: Yash Shah

DIFFICULTY:

EASY-MEDIUM

PROBLEM:

There is a Band Procession which requires singer S to stand first and
the pianist P to stand at last.

The Band Procession can be represented as ‘S.P’ (there can be any
number of ‘.’).

The bands come in procession, but one by one. A valid procession
will be ‘S….P’ or ‘S…P’ or ‘S…P…S……P’ whereas ‘S.P.S’ or
‘S.S….P…S’ are invalid.

You are given task to identify whether a Band Procession is Valid or
Invalid.

Input Format:

  • The first line contains a single integer, T, which denotes the
    number of test cases to be checked. The description of each test
    case follows this.
  • The first line of each report contains a single integerL which
    indicates the length of that report.
  • The second line of each report contains a string of length L. The
    string contains only the characters ‘.’, ‘S’, and ‘P’.

Output Format:

  • For each test case, output the string Valid or Invalid in a new line,
    depending on whether it was a valid Band Procession or not.

EXPLANATION:

Sample Test Case:

Input:
6
18
…S…P…SPS…P.
3
…
10
S…S…P…P
2
SP
11
.P…S…S.P
7
S…P…S

Output:
Valid
Invalid
Invalid
Valid
Invalid
Invalid

Test Case 1: “S…S…P…P” is invalid because the second Band
starts before the first Band ends, which is not allowed.
• Test Case 2: “.P…S…S.P” is invalid because it has a ‘P’ before a
‘S’. A Pianist can come only after its Band’s Singer.
• Test Case 3: “S…P…S” is invalid because the last ‘S’ does not have
a corresponding ‘P’.

SOLUTIONS:

Setter's Solution 
for __ in range(int(input())):
    N = int(input())
    S = input().replace('.', '')
    if S.count('S') != S.count('P') or S.replace('SP', '') != '':
        print('Invalid')
    else:
        print('Valid')