Hello everyone, I recently had my online assessment for new grad role at google. I want to post a question which was asked, and seek help from the community in solving this problem. The problem was:

PR Strings

You are given a string S (consisting of lowercase English characters).

In one operation, you can remove the substring "pr" from the string S and get the amount X or you can remove the substring "rp" from the string S and get the amount Y.
Find the maximum amount you can get if you perfrom zero or more such operations optimally.

Note:

• Substring of a string S is defined as a continuous sequence of characters in S.
• After removal of substring "pr" or "rp" from S rest of the characters in S remains in same order.

Input format

• First Line contains an integer T denoting no of test cases.
• First Line of each test case contains a String S.
• Second Line of each test case contains two space-seperated integers X and Y.

Output

• For each test case print an integer denoting maximum amount you can get in a new line.

Example
Sample Input

3
abppprrr
5 4
prprprrp
7 10
abcdpqrpqr
3 4

Sample Output

15
37
4

Explanation:
Test Case 1:
S = "abppprrr", X=5, Y=4

Remove substrings as mentioned:

• Remove "pr", new string S = "abpprr".
• Remove "pr", new string S = "abpr".
• Remove "pr", new string S = "ab".

In total we remove "pr" 3 times. Hence answer is 3*X=15.

Test Case 2:
S = "prprprrp", X=7, Y=10

Remove substrings as mentioned:

• Remove "rp", new string S = "prprrp"
• Remove "rp", new string S = "prrp"
• Remove "rp", new string S = "pr"
• Remove "pr", new String S = "" (Empty String)

In total we remove "rp" 3 times and "pr" 1 times. Hence answer is 3Y + 1X = 37.

Sample python function:

def solve(S, X, Y):
	#Code goes here

Thanks in advance.