Given a string S. In one operation, you can remove the substring "pr" from the string S and get amount X or you can remove the substring "rp" and get the amount Y. 
Find the maximum amount you can get if you perform zero or more such operations optimally. 
Note : 
	Substring of a string S is defined as a continuous sequence of characters in S.
	After removing pr or rp, the order of remaining letters should remain the same.
Example 1:
Input:
X = 5, Y = 4
S = "abppprrr"
Output: 15
Explanation: 
Here, S = "abppprrr" 
X= 5, Y=4.
Remove "pr", new string S = "abpprr".
Remove "pr", new string S = "abpr".
Remove "pr", new string S = "ab".
In total, we removed "pr" 3 times, 
so total score is 3*X + 0*Y = 3*5 =15.
 
 
Example 2:
Input:
X = 7, Y = 7
S = "prpptppr"
Output: 14
Explanation: 
Here, S = "prpptppr" 
X= 7, Y=7.
As both have the same amount we can first 
remove either pr or rp. Here we start with pr
Remove "pr", new string S = "pptppr".
Remove "pr", new string S = "pptp".
In total, we removed "pr" 2 times, 
so total score is 2*X + 0*Y = 2*7 =14.
Your Task: 
You don't need to read input or print anything. Your task is to complete the function solve() which takes the X ,Y and string S as input parameters and returns the maximum amount you can get after performing the above operations.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|S|)
Constraints:
1 ≤ |S| ≤ 10^{5}
1 ≤ X,Y ≤ 10^{5}
S contains lowercase English letters only.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def solve (self, X, Y, S):

        #code here

Solutions:
class Solution:

	def solve(self, X, Y, S):

		def find(st, cost, stri):
			stac = ['$']
			ans = 0
			for i in stri:
				stac.append(i)
				if stac[-2] == st[0] and stac[-1] == st[1]:
					stac.pop()
					stac.pop()
					ans += cost
			return (ans, ''.join(stac[1:]))
		if X > Y:
			(gain, st) = find('pr', X, S)
			(c, _) = find('rp', Y, st)
			return gain + c
		else:
			(gain, st) = find('rp', Y, S)
			(c, _) = find('pr', X, st)
			return gain + c


class Solution:

	def solve(self, X, Y, S):
		ret = 0
		stk = list(S)
		q = ['pr', 'rp']
		if Y > X:
			q = ['rp', 'pr']
			(X, Y) = (Y, X)
		amt = X
		for i in q:
			S = list(stk)
			stk.clear()
			for j in S:
				if stk and stk[-1] == i[0] and (j == i[1]):
					stk.pop()
					ret += amt
				else:
					stk.append(j)
			amt = Y
		return ret


class Solution:

	def solve(self, X, Y, S):

		def help(S, st, value, ans):
			stack = []
			stack.append(S[0])
			for i in range(1, len(S)):
				if S[i] == st[1]:
					if stack != []:
						if stack[len(stack) - 1] == st[0]:
							stack.pop()
							ans += value
							continue
				stack.append(S[i])
			temp = ''
			for i in stack:
				temp += i
			return (temp, ans)
		if X > Y:
			(temp1, ans) = help(S, 'pr', X, 0)
			(temp1, ans) = help(temp1, 'rp', Y, ans)
			return ans
		else:
			(temp1, ans) = help(S, 'rp', Y, 0)
			(temp1, ans) = help(temp1, 'pr', X, ans)
			return ans


class Solution:

	def solve(self, X, Y, S):
		len(S)
		stk = []
		major = 'pr'
		minor = 'rp'
		score = 0
		if X < Y:
			(major, minor) = (minor, major)
			(X, Y) = (Y, X)
		for c in S:
			if len(stk) == 0:
				stk.append(c)
				continue
			word = stk[-1] + c
			if word == major:
				score += X
				stk.pop()
			else:
				stk.append(c)
		stk2 = []
		for c in stk:
			if len(stk2) == 0:
				stk2.append(c)
				continue
			word = stk2[-1] + c
			if word == minor:
				score += Y
				stk2.pop()
			else:
				stk2.append(c)
		return score


class Solution:

	def solve(self, X, Y, S):

		def helper(string, t):
			x = []
			count = 0
			for i in string:
				if not x:
					x.append(i)
				elif i == t[1] and x[-1] == t[0]:
					x.pop()
					count += 1
				else:
					x.append(i)
			return [''.join(x), count]
		if X > Y:
			t = helper(S, 'pr')
			ans = t[1] * X
			tt = helper(t[0], 'rp')
			ans += tt[1] * Y
			return ans
		else:
			t = helper(S, 'rp')
			ans = t[1] * Y
			tt = helper(t[0], 'pr')
			ans += tt[1] * X
			return ans


class Solution:

	def solve(self, x, y, s):
		n = len(s)
		(a, b) = (0, 0)
		ind = 0
		c = ''
		if x >= y:
			c = 'pr'
		else:
			c = 'rp'
			ind = 1
		l = []
		for i in s:
			if len(l):
				s = l[-1] + i
				if s == c:
					l.pop(-1)
					a += 1
				else:
					l.append(i)
			else:
				l.append(i)
		s = ''.join([i for i in l])
		l.clear()
		c = c[::-1]
		for i in s:
			if len(l):
				s = l[-1] + i
				if s == c:
					l.pop(-1)
					b += 1
				else:
					l.append(i)
			else:
				l.append(i)
		if ind:
			return a * y + b * x
		return a * x + b * y


class Solution:

	def solve(self, X, Y, S):
		s = s1 = S
		score1 = 0
		score2 = 0
		while True:
			while s.count('pr') != 0:
				score1 += s.count('pr') * X
				s = s.replace('pr', '')
			while s.count('rp') != 0:
				score1 += s.count('rp') * Y
				s = s.replace('rp', '')
			while s1.count('rp') != 0:
				score2 += s1.count('rp') * Y
				s1 = s1.replace('rp', '')
			while s1.count('pr') != 0:
				score2 += s1.count('pr') * X
				s1 = s1.replace('pr', '')
			if s.count('pr') == 0 and s.count('rp') == 0 or (s1.count('pr') == 0 and s1.count('rp') == 0):
				break
		return max(score1, score2)


class Solution:

	def solve(self, X, Y, S):
		x = 0
		y = 0
		while 'pr' in S or 'rp' in S:
			if X >= Y:
				while 'pr' in S:
					x += S.count('pr')
					S = S.replace('pr', '')
				while 'rp' in S:
					y += S.count('rp')
					S = S.replace('rp', '')
			else:
				while 'rp' in S:
					y += S.count('rp')
					S = S.replace('rp', '')
				while 'pr' in S:
					x += S.count('pr')
					S = S.replace('pr', '')
		return X * x + Y * y


class Solution:

	def solve(self, X, Y, S):
		stack = []
		ans = 0
		for x in S:
			if len(stack) == 0:
				stack.append(x)
			else:
				top = stack[-1]
				if X >= Y and top == 'p' and (x == 'r'):
					stack.pop()
					ans += X
				elif X < Y and top == 'r' and (x == 'p'):
					stack.pop()
					ans += Y
				else:
					stack.append(x)
		if X >= Y:
			(b0, b1) = ('r', 'p')
			inc = Y
		else:
			(b0, b1) = ('p', 'r')
			inc = X
		S = ''.join(stack)
		stack = []
		for x in S:
			if len(stack) == 0:
				stack.append(x)
			elif stack[-1] == b0 and x == b1:
				ans += inc
				stack.pop()
			else:
				stack.append(x)
		return ans


class Solution:

	def solve(self, X, Y, S):
		result = 0
		flag = True
		while flag:
			if 'pr' in S and 'rp' in S:
				if X > Y:
					count = S.count('pr')
					result += X * count
					S = S.replace('pr', '', count)
				elif X < Y:
					count = S.count('rp')
					result += Y * count
					S = S.replace('rp', '', count)
				else:
					count = S.count('pr')
					S = S.replace('pr', '', count)
					result += X * count
					if 'rp' in S:
						count = S.count('rp')
						S = S.replace('rp', '', count)
						result += Y * count
			elif 'pr' in S:
				count = S.count('pr')
				result += X * count
				S = S.replace('pr', '', count)
			elif 'rp' in S:
				count = S.count('rp')
				result += Y * count
				S = S.replace('rp', '', count)
			else:
				flag = 0
		return result


class Solution:

	def solve(self, X, Y, S):
		stk = []
		s1 = 'pr'
		s2 = 'rp'
		ans = 0
		if X < Y:
			temp = 0
			temp = X
			X = Y
			Y = temp
			t = ''
			t = s1
			s1 = s2
			s2 = t
		for i in range(len(S) - 1, -1, -1):
			if S[i] == s1[0] and len(stk) > 0 and (stk[-1] == s1[1]):
				ans += X
				stk.pop()
			else:
				stk.append(S[i])
		my_str = ' '
		while len(stk) > 0:
			t = stk.pop()
			my_str += t
		for j in range(len(my_str) - 1, -1, -1):
			if len(stk) > 0 and my_str[j] == s2[0] and (stk[-1] == s2[1]):
				ans += Y
				stk.pop()
			else:
				stk.append(my_str[j])
		return ans


class Solution:

	def solve(self, x, y, s):
		ans = [0]

		def solve(l, exp, val):
			st = []
			for i in l:
				if i == exp[1]:
					if st and st[-1] == exp[0]:
						st.pop()
						ans[0] += val
					else:
						st.append(i)
				else:
					st.append(i)
			return st
		if X > Y:
			s = solve(list(S), 'pr', X)
			solve(s, 'rp', Y)
		else:
			s = solve(list(S), 'rp', Y)
			solve(s, 'pr', X)
		return ans[0]


class Solution:

	def solve(self, X, Y, S):
		c1 = 'p'
		c2 = 'r'
		if X < Y:
			c1 = 'r'
			c2 = 'p'
			t = X
			X = Y
			Y = t
		s = []
		ans = 0
		for (i, c) in enumerate(S):
			if not s:
				s.append(c)
			elif s[-1] == c1 and c == c2:
				ans += X
				s.pop(-1)
			else:
				s.append(c)
		s1 = []
		for c in s:
			if not s1:
				s1.append(c)
			elif s1[-1] == c2 and c == c1:
				ans += Y
				s1.pop(-1)
			else:
				s1.append(c)
		return ans


class Solution:

	def solve(self, X, Y, S):
		(stack, stack2, x, y, k, z, ch) = ([], [], 0, 0, '', '', True)
		if X > Y:
			k = 'r'
			z = 'p'
		else:
			k = 'p'
			z = 'r'
			ch = False
		for i in S:
			if stack and i == k and (stack[len(stack) - 1] == z):
				stack.pop()
				if ch == True:
					x += 1
				else:
					y += 1
			else:
				stack.append(i)
		g = ''.join([i for i in stack])
		for i in g:
			if stack2 and i == z and (stack2[len(stack2) - 1] == k):
				stack2.pop()
				if ch == True:
					y += 1
				else:
					x += 1
			else:
				stack2.append(i)
		return X * x + Y * y


class Solution:

	def solve(self, X, Y, S):
		answer = 0
		a = 'pr'
		b = 'rp'
		if X < Y:
			(X, Y) = (Y, X)
			(a, b) = (b, a)
		st = []
		for i in range(len(S) - 1, -1, -1):
			if len(st) > 0 and S[i] == a[0] and (st[-1] == a[1]):
				st.pop(len(st) - 1)
				answer += X
			else:
				st.append(S[i])
		S = ''
		while len(st) > 0:
			S += st[-1]
			st.pop(len(st) - 1)
		for i in range(len(S) - 1, -1, -1):
			if len(st) > 0 and S[i] == b[0] and (st[-1] == b[1]):
				st.pop(len(st) - 1)
				answer += Y
			else:
				st.append(S[i])
		return answer


class Solution:

	def solve(self, X, Y, S):
		s = []
		c = 0
		l = len(S)
		if X >= Y:
			for i in S:
				if i == 'r' and s and (s[-1] == 'p'):
					s.pop()
					c += X
				else:
					s.append(i)
			S = ''.join(s)
			s = []
			for i in S:
				if i == 'p' and s and (s[-1] == 'r'):
					s.pop()
					c += Y
				else:
					s.append(i)
		else:
			for i in S:
				if i == 'p' and s and (s[-1] == 'r'):
					s.pop()
					c += Y
				else:
					s.append(i)
			S = ''.join(s)
			s = []
			for i in S:
				if i == 'r' and s and (s[-1] == 'p'):
					s.pop()
					c += X
				else:
					s.append(i)
		return c


from collections import Counter

class Solution:

	def solve(self, X, Y, S):
		(x, y) = (0, 0)
		while True:
			if X >= Y:
				if 'pr' in S:
					x += S.count('pr')
					S = S.replace('pr', '')
				elif 'rp' in S:
					y += S.count('rp')
					S = S.replace('rp', '')
				else:
					break
			if Y > X:
				if 'rp' in S:
					y += S.count('rp')
					S = S.replace('rp', '')
				elif 'pr' in S:
					x += S.count('pr')
					S = S.replace('pr', '')
				else:
					break
		return x * X + y * Y


class Solution1:

	def solve(self, X, Y, S):
		ans = [0]

		def help(l, exp, val, ans):
			stack = []
			for i in l:
				if i == exp[1] and stack and (stack[-1] == exp[0]):
					stack.pop()
					ans[0] += val
				else:
					stack.append(i)
			return stack
		if X > Y:
			s = help(S, 'pr', X, ans)
			s = help(s, 'rp', Y, ans)
		else:
			s = help(S, 'rp', Y, ans)
			s = help(s, 'pr', X, ans)
		return ans[0]

class Solution:

	def solve(self, X, Y, S):
		x = 0
		y = 0
		if X >= Y:
			while 'pr' in S:
				x += S.count('pr')
				S = S.replace('pr', '')
			while 'rp' in S:
				y += S.count('rp')
				S = S.replace('rp', '')
		else:
			while 'rp' in S:
				y += S.count('rp')
				S = S.replace('rp', '')
			while 'pr' in S:
				x += S.count('pr')
				S = S.replace('pr', '')
		return X * x + Y * y


class Solution:

	def solve(self, X, Y, S):
		ans = [0]

		def help(l, exp, val, ans):
			stack = []
			for i in l:
				if i == exp[1] and stack and (stack[-1] == exp[0]):
					stack.pop()
					ans[0] += val
				else:
					stack.append(i)
			return stack
		if X > Y:
			s = help(S, 'pr', X, ans)
			s = help(s, 'rp', Y, ans)
		else:
			s = help(S, 'rp', Y, ans)
			s = help(s, 'pr', X, ans)
		return ans[0]


class Solution:

	def solve(self, X, Y, S):
		l = len(S)
		str1 = 'pr'
		str2 = 'rp'
		if Y > X:
			str1 = 'rp'
			str2 = 'pr'
			(X, Y) = (Y, X)
		while str1 in S:
			S = S.replace(str1, '')
		x = (l - len(S)) // 2
		l = len(S)
		while str2 in S:
			S = S.replace(str2, '')
		y = (l - len(S)) // 2
		l = len(S)
		return X * x + Y * y


class Solution:

	def solve(self, X, Y, S):
		out = 0
		(stack1, stack2) = ([], [])
		(val1, val2) = (X, Y) if X > Y else (Y, X)
		(ch1, ch2) = ('p', 'r') if X > Y else ('r', 'p')
		for i in range(len(S)):
			if len(stack1) > 0 and stack1[-1] == ch1 and (S[i] == ch2):
				stack1.pop()
				out += val1
			else:
				stack1.append(S[i])
		while len(stack1) > 0:
			if len(stack2) > 0 and stack2[-1] == ch1 and (stack1[-1] == ch2):
				stack2.pop()
				stack1.pop()
				out += val2
			else:
				stack2.append(stack1.pop())
		return out


class Solution:

	def solve(self, X, Y, s):
		i = 0
		stk = []
		ans = 0
		c_p = 0
		c_r = 0
		if X >= Y:
			while i < len(s):
				if s[i] == 'p':
					stk.append(s[i])
				elif s[i] == 'r':
					if len(stk) > 0 and stk[-1] == 'p':
						ans += X
						stk.pop()
					else:
						stk.append(s[i])
				elif len(stk) != 0:
					while len(stk) != 0:
						if stk[-1] == 'p':
							c_p += 1
						else:
							c_r += 1
						stk.pop()
					ans += min(c_p, c_r) * Y
					c_p = 0
					c_r = 0
				i += 1
			if i == len(s) and len(stk) != 0:
				while len(stk) != 0:
					if stk[-1] == 'p':
						c_p += 1
					else:
						c_r += 1
					stk.pop()
				ans += min(c_p, c_r) * Y
		else:
			while i < len(s):
				if s[i] == 'r':
					stk.append(s[i])
				elif s[i] == 'p':
					if len(stk) > 0 and stk[-1] == 'r':
						ans += Y
						stk.pop()
					else:
						stk.append(s[i])
				elif len(stk) != 0:
					while len(stk) != 0:
						if stk[-1] == 'p':
							c_p += 1
						else:
							c_r += 1
						stk.pop()
					ans += min(c_p, c_r) * X
					c_p = 0
					c_r = 0
				i += 1
			if i == len(s) and len(stk) != 0:
				while len(stk) != 0:
					if stk[-1] == 'p':
						c_p += 1
					else:
						c_r += 1
					stk.pop()
				ans += min(c_p, c_r) * X
		return ans


class Solution:

	def solve(self, X, Y, S):
		if X > Y:
			c = 0
			s = []
			i = 0
			while i < len(S):
				if len(s) == 0:
					s.append(S[i])
					i = i + 1
				elif S[i] == 'r':
					if s[-1] == 'p':
						s.pop()
						i = i + 1
						c = c + X
					else:
						s.append(S[i])
						i = i + 1
				else:
					s.append(S[i])
					i = i + 1
			S = ''
			for i in s:
				S = S + i
			s = []
			i = 0
			while i < len(S):
				if len(s) == 0:
					s.append(S[i])
					i = i + 1
				elif S[i] == 'p':
					if s[-1] == 'r':
						s.pop()
						i = i + 1
						c = c + Y
					else:
						s.append(S[i])
						i = i + 1
				else:
					s.append(S[i])
					i = i + 1
			return c
		else:
			c = 0
			s = []
			i = 0
			while i < len(S):
				if len(s) == 0:
					s.append(S[i])
					i = i + 1
				elif S[i] == 'p':
					if s[-1] == 'r':
						s.pop()
						i = i + 1
						c = c + Y
					else:
						s.append(S[i])
						i = i + 1
				else:
					s.append(S[i])
					i = i + 1
			S = ''
			for i in s:
				S = S + i
			s = []
			i = 0
			while i < len(S):
				if len(s) == 0:
					s.append(S[i])
					i = i + 1
				elif S[i] == 'r':
					if s[-1] == 'p':
						s.pop()
						i = i + 1
						c = c + X
					else:
						s.append(S[i])
						i = i + 1
				else:
					s.append(S[i])
					i = i + 1
			return c


import re

class Solution:

	def solve(self, X, Y, S):
		l = len(S)
		str1 = 'pr'
		str2 = 'rp'
		if X < Y:
			(X, Y) = (Y, X)
			(str1, str2) = (str2, str1)
		while str1 in S:
			S = re.sub(str1, '', S)
		x = (l - len(S)) // 2
		l = len(S)
		while str2 in S:
			S = re.sub(str2, '', S)
		y = (l - len(S)) // 2
		return X * x + Y * y


class Solution:

	def solve(self, X, Y, S):

		def helper(s, toSearch):
			stack = []
			i = 0
			while i < len(s):
				if s[i] == toSearch[1] and stack and (stack[-1] == toSearch[0]):
					stack.pop()
				else:
					stack.append(s[i])
				i += 1
			return ''.join(stack)
		ans = 0
		if X > Y:
			ns = helper(S, 'pr')
			ans += X * (len(S) - len(ns)) // 2
			ns2 = helper(ns, 'rp')
			ans += Y * (len(ns) - len(ns2)) // 2
			return ans
		else:
			ns = helper(S, 'rp')
			ans += Y * (len(S) - len(ns)) // 2
			ns2 = helper(ns, 'pr')
			ans += X * (len(ns) - len(ns2)) // 2
			return ans


from collections import deque

class Solution:

	def solve(self, X, Y, S):
		answer = 0
		a = 'pr'
		b = 'rp'
		if X < Y:
			(X, Y) = (Y, X)
			(a, b) = (b, a)
		st = deque()
		for i in range(len(S) - 1, -1, -1):
			if len(st) > 0 and S[i] == a[0] and (st[-1] == a[1]):
				st.pop()
				answer += X
			else:
				st.append(S[i])
		S = ''.join(reversed(st))
		st.clear()
		for i in range(len(S) - 1, -1, -1):
			if len(st) > 0 and S[i] == b[0] and (st[-1] == b[1]):
				st.pop()
				answer += Y
			else:
				st.append(S[i])
		return answer


class Solution:

	def solve(self, X, Y, s):
		score = 0
		if X > Y:
			ns = self.pr(s)
			score += X * ((len(s) - len(ns)) // 2)
			s = ns
			ns = self.rp(s)
			score += Y * ((len(s) - len(ns)) // 2)
		else:
			ns = self.rp(s)
			score += Y * ((len(s) - len(ns)) // 2)
			s = ns
			ns = self.pr(s)
			score += X * ((len(s) - len(ns)) // 2)
		return score

	def pr(self, s):
		i = 1
		ns = [s[0]]
		while i < len(s):
			if ns == [] or ns[-1] + s[i] != 'pr':
				ns.append(s[i])
			else:
				ns.pop(len(ns) - 1)
			i += 1
		return ns

	def rp(self, s):
		i = 1
		ns = [s[0]]
		while i < len(s):
			if ns == [] or ns[-1] + s[i] != 'rp':
				ns.append(s[i])
			else:
				ns.pop(len(ns) - 1)
			i += 1
		return ns


from collections import deque

class Solution:

	def solve(self, X, Y, S):
		ans = 0
		str1 = 'pr'
		str2 = 'rp'
		if X < Y:
			(X, Y) = (Y, X)
			(str1, str2) = (str2, str1)
		list_of_stack = deque()
		for i in range(len(S) - 1, -1, -1):
			if len(list_of_stack) > 0 and S[i] == str1[0] and (list_of_stack[-1] == str1[1]):
				list_of_stack.pop()
				ans += X
			else:
				list_of_stack.append(S[i])
		S = ''.join(reversed(list_of_stack))
		list_of_stack.clear()
		for i in range(len(S) - 1, -1, -1):
			if len(list_of_stack) > 0 and S[i] == str2[0] and (list_of_stack[-1] == str2[1]):
				list_of_stack.pop()
				ans += +Y
			else:
				list_of_stack.append(S[i])
		return ans


def remPR(arr):
	s = []
	count = 0
	for val in arr:
		if len(s) and val == 'r' and (s[-1] == 'p'):
			count += 1
			s.pop()
		else:
			s.append(val)
	return [s, count]

def remRP(arr):
	s = []
	count = 0
	for val in arr:
		if len(s) and val == 'p' and (s[-1] == 'r'):
			count += 1
			s.pop()
		else:
			s.append(val)
	return [s, count]

class Solution:

	def solve(self, X, Y, S):
		S = list(S)
		stack = []
		amount = 0
		if X > Y:
			(s, count) = remPR(S)
			amount += count * X
			(k, count) = remRP(s)
			amount += count * Y
		else:
			(s, count) = remRP(S)
			amount += count * Y
			(k, count) = remPR(s)
			amount += count * X
		return amount


class Solution:

	def getVal(self, s, cs):
		st = []
		n = len(s)
		ans = 0
		for i in range(0, n):
			if st and st[-1] + s[i] == cs:
				ans += 1
				st.pop()
			else:
				st.append(s[i])
		return [''.join(st), ans]

	def solve(self, X, Y, S):
		if X >= Y:
			l1 = self.getVal(S, 'pr')
			S = l1[0]
			l2 = self.getVal(S, 'rp')
			return l1[1] * X + l2[1] * Y
		else:
			l1 = self.getVal(S, 'rp')
			S = l1[0]
			l2 = self.getVal(S, 'pr')
			return l1[1] * Y + l2[1] * X


class Solution:

	def solve(self, X, Y, S):
		x_count = 0
		y_count = 0
		while 'pr' in S or 'rp' in S:
			if X >= Y:
				while 'pr' in S:
					x_count = x_count + S.count('pr')
					S = S.replace('pr', '')
				while 'rp' in S:
					y_count = y_count + S.count('rp')
					S = S.replace('rp', '')
			else:
				while 'rp' in S:
					y_count = y_count + S.count('rp')
					S = S.replace('rp', '')
				while 'pr' in S:
					x_count = x_count + S.count('pr')
					S = S.replace('pr', '')
		return x_count * X + y_count * Y


class Solution:

	def solve(self, X, Y, S):
		fr = 0
		sc = 0
		S2 = S
		if X >= Y:
			while 'pr' in S:
				f = len(S)
				S = S.replace('pr', '')
				a = len(S)
				fr += X * (f - a) / 2
			while 'rp' in S:
				f = len(S)
				S = S.replace('rp', '')
				a = len(S)
				fr += Y * (f - a) / 2
		else:
			while 'rp' in S2:
				f = len(S2)
				S2 = S2.replace('rp', '')
				a = len(S2)
				sc += Y * (f - a) / 2
			while 'pr' in S2:
				f = len(S2)
				S2 = S2.replace('pr', '')
				a = len(S2)
				sc += X * (f - a) / 2
		return int(fr) if fr >= sc else int(sc)


class Solution:

	def solve(self, X, Y, S):
		check_1 = 'pr'
		check_2 = 'rp'
		if Y > X:
			(X, Y) = (Y, X)
			(check_1, check_2) = (check_2, check_1)
		count = 0
		stack = []
		for ch in S:
			if not stack or stack[-1] + ch != check_1:
				stack.append(ch)
			else:
				stack.pop()
				count += X
		S = stack.copy()
		stack.clear()
		for ch in S:
			if not stack or stack[-1] + ch != check_2:
				stack.append(ch)
			else:
				stack.pop()
				count += Y
		return count


class Solution:

	def solve(self, X, Y, S):
		ans = 0
		a = ''
		b = ''
		if X < Y:
			a = 'rp'
			b = 'pr'
			temp = X
			X = Y
			Y = temp
		else:
			a = 'pr'
			b = 'rp'
		stack = []
		for i in range(0, len(S)):
			if len(stack) == 0:
				stack.append(S[i])
			elif S[i] == a[1] and stack[-1] == a[0]:
				ans += X
				stack.pop()
			else:
				stack.append(S[i])
		S = ''.join(stack)
		stack.clear()
		for i in range(0, len(S)):
			if len(stack) == 0:
				stack.append(S[i])
			elif S[i] == b[1] and stack[-1] == b[0]:
				ans += Y
				stack.pop()
			else:
				stack.append(S[i])
		return ans


class Solution:

	def solve(self, x, y, s):
		ans = 0
		if x > y:
			ans = self.help(x, y, s, 'pr')
		else:
			ans = self.help(y, x, s, 'rp')
		return ans

	def help(self, x, y, s, rem):
		total = 0
		stack = []
		for i in range(len(s)):
			if len(stack) != 0 and s[i] == rem[1] and (stack[-1] == rem[0]):
				total += x
				stack.pop()
			else:
				stack.append(s[i])
		s = ''
		while stack:
			a = stack.pop()
			s += a
		for i in range(len(s)):
			if len(stack) != 0 and s[i] == rem[1] and (stack[-1] == rem[0]):
				total += y
				stack.pop()
			else:
				stack.append(s[i])
		return total


class Solution:

	def help(self, X, Y, S, curr):
		st = []
		ans = 0
		for i in range(0, len(S)):
			if st and S[i] == curr[1] and (st[-1] == curr[0]):
				st.pop()
				ans += X
			else:
				st.append(S[i])
		S = ''.join(st)
		st = []
		for i in range(0, len(S)):
			if st and S[i] == curr[0] and (st[-1] == curr[1]):
				st.pop()
				ans += Y
			else:
				st.append(S[i])
		return ans

	def solve(self, X, Y, S):
		ans = 0
		if X > Y:
			ans = self.help(X, Y, S, 'pr')
		else:
			ans = self.help(Y, X, S, 'rp')
		return ans


class Solution:

	def __init__(self):
		self.stack = self.Stack()

	class Stack:

		def __init__(self):
			self.arr = []

		def push(self, ch):
			self.arr.append(ch)

		def pop(self):
			self.arr.pop()

		def top(self):
			return self.arr[-1]

		def isempty(self):
			return not self.arr

		def empty_stack(self):
			self.arr.clear()

		def return_elements(self):
			return self.arr

	def solve(self, X, Y, S):
		check_1 = 'pr'
		check_2 = 'rp'
		if Y > X:
			(X, Y) = (Y, X)
			(check_1, check_2) = (check_2, check_1)
		count = 0
		count += self.count_str(S, check_1, X)
		S = self.stack.return_elements().copy()
		self.stack.empty_stack()
		count += self.count_str(S, check_2, Y)
		return count

	def count_str(self, S, string, val):
		count = 0
		for ch in S:
			if self.stack.isempty():
				self.stack.push(ch)
				continue
			top = self.stack.top()
			s = top + ch
			if s == string:
				self.stack.pop()
				count += val
			else:
				self.stack.push(ch)
		return count


class Solution:

	def solve(self, X, Y, S):
		res = [0]
		if X > Y:
			self.pr(X, Y, S, res, True)
		else:
			self.rp(X, Y, S, res, True)
		return res[0]

	def pr(self, X, Y, S, res, flag):
		stack = []
		for c in S:
			if c == 'r':
				if stack and stack[-1] == 'p':
					res[0] += X
					stack.pop()
				else:
					stack.append(c)
			else:
				stack.append(c)
		if flag:
			self.rp(X, Y, ''.join(stack), res, False)

	def rp(self, X, Y, S, res, flag):
		stack = []
		for c in S:
			if c == 'p':
				if stack and stack[-1] == 'r':
					res[0] += Y
					stack.pop()
				else:
					stack.append(c)
			else:
				stack.append(c)
		if flag:
			self.pr(X, Y, ''.join(stack), res, False)


class Solution:

	def getAns(self, x, s, p):
		ans = 0
		stack = []
		l = len(s)
		for i in range(l):
			stack.append(s[i])
			if len(stack) > 1:
				last = ''.join(stack[-2:])
				if last == p:
					ans += x
					stack.pop()
					stack.pop()
		s = ''.join(stack)
		return [ans, s]

	def solve(self, X, Y, s):
		ans = 0
		p = 'pr'
		r = 'rp'
		if X < Y:
			(Y, X) = (X, Y)
			(p, r) = (r, p)
		res = self.getAns(X, s, p)
		ans += res[0]
		s = res[1]
		ans += self.getAns(Y, s, r)[0]
		return ans


class Solution:

	def solve(self, X, Y, S):
		if X >= Y:
			length = len(S)
			count_pr = 0
			count_rp = 0
			while 'pr' in S:
				S = S.replace('pr', '')
			count_pr = (length - len(S)) / 2
			while 'rp' in S:
				S = S.replace('rp', '')
			count_rp = (length - count_pr * 2 - len(S)) / 2
		else:
			length = len(S)
			count_pr = 0
			count_rp = 0
			while 'rp' in S:
				S = S.replace('rp', '')
				count_rp = (length - len(S)) / 2
			while 'pr' in S:
				S = S.replace('pr', '')
				count_pr = (length - count_rp * 2 - len(S)) / 2
		mul_x = count_pr
		mul_y = count_rp
		return int(X * mul_x + Y * mul_y)


class Solution:

	def solve(self, X, Y, S):
		s = []
		ans = [0]

		def call():
			p = s.pop()
			e = []
			while len(s) > 0:
				q = s.pop()
				if p == 'r' and q == 'p':
					ans[0] += X
					if len(e) > 0:
						p = e.pop()
					elif len(s) > 0:
						p = s.pop()
				elif p == 'p' and q == 'r':
					ans[0] += Y
					if len(e) > 0:
						p = e.pop()
					elif len(s) > 0:
						p = s.pop()
				else:
					e.append(p)
					p = q
		for i in S:
			s.append(i)
			if i != 'p' and i != 'r':
				call()
			if X > Y:
				if i == 'r':
					if len(s) > 1:
						if s[-2] == 'p':
							ans[0] += X
							s.pop()
							s.pop()
			elif i == 'p':
				if len(s) > 1:
					if s[-2] == 'r':
						ans[0] += Y
						s.pop()
						s.pop()
		if len(s) > 0:
			call()
		return ans[0]


class Solution:

	def solve(self, X, Y, S):
		if X >= Y:
			order = [('pr', X), ('rp', Y)]
		else:
			order = [('rp', Y), ('pr', X)]
		ans = 0
		for ((c0, c1), score) in order:
			(N, NS) = (len(S), [])
			for i in range(N):
				NS.append(S[i])
				if S[i] == c1 and len(NS) > 1 and (NS[-2] == c0):
					ans += score
					NS.pop()
					NS.pop()
			S = NS
		return ans


class Solution:

	def solve(self, X, Y, S):
		n = len(S)
		o = []
		for char in S:
			o.append(char)
		if Y > X:
			(X, Y) = (Y, X)
			for i in range(n):
				if o[i] == 'p':
					o[i] = 'r'
				elif o[i] == 'r':
					o[i] = 'p'
			S = ''.join(o)
		res = 0
		countP = 0
		countR = 0
		for i in range(n):
			if S[i] == 'p':
				countP += 1
			elif S[i] == 'r':
				if countP > 0:
					countP -= 1
					res += X
				else:
					countR += 1
			else:
				res += min(countP, countR) * Y
				countP = 0
				countR = 0
		res += min(countP, countR) * Y
		return res


class Solution:

	def solve(self, x, y, s):
		count = 0
		c = []
		if x >= y:
			c.append('pr')
			c.append('rp')
		else:
			c.append('rp')
			c.append('pr')
		l = []
		for i in s:
			if i != c[0][1]:
				l.append(i)
			elif len(l) != 0 and l[-1] == c[0][0]:
				l.pop()
				count = count + max(x, y)
			else:
				l.append(i)
		c.remove(c[0])
		s = ''
		for j in l:
			s = s + j
		l = []
		for i in s:
			if i != c[0][1]:
				l.append(i)
			elif len(l) != 0 and l[-1] == c[0][0]:
				l.pop()
				count = count + min(x, y)
			else:
				l.append(i)
		return count


class Solution:

	def solve(self, X, Y, S):
		amount = 0
		while 'pr' in S or 'rp' in S:
			if 'pr' in S and 'rp' in S:
				if X > Y:
					l = S.split('pr')
					amount += X * (len(l) - 1)
					S = ''.join(l)
				else:
					l = S.split('rp')
					amount += Y * (len(l) - 1)
					S = ''.join(l)
			elif 'pr' in S:
				l = S.split('pr')
				amount += X * (len(l) - 1)
				S = ''.join(l)
			elif 'rp' in S:
				l = S.split('rp')
				amount += Y * (len(l) - 1)
				S = ''.join(l)
			else:
				return amount
		return amount


class Solution:

	def solve(self, X, Y, S):
		sc = {'pr': X, 'rp': Y}
		msc = max(X, Y)
		(ans, stack) = (0, [])
		for e in S:
			if e not in 'pr':
				if stack:
					pn = stack.count('p')
					ans += min(pn, len(stack) - pn) * min(X, Y)
					stack.clear()
			elif stack and sc.get(stack[-1] + e, 0) == msc:
				stack.pop()


def sol1(X, Y, S, stack):
	cnt = 0
	for i in range(len(S)):
		if not stack:
			stack.append(S[i])
		elif stack[-1] == 'p' and S[i] == 'r':
			cnt += 1
			stack.pop()
		else:
			stack.append(S[i])
	return cnt

def sol2(X, Y, S, stack):
	cnt = 0
	for i in range(len(S)):
		if not stack:
			stack.append(S[i])
		elif stack[-1] == 'r' and S[i] == 'p':
			cnt += 1
			stack.pop()
		else:
			stack.append(S[i])
	return cnt

class Solution:

	def solve(self, X, Y, S):
		(stack1, stack2) = ([], [])
		res = 0
		if X >= Y:
			a = sol1(X, Y, S, stack1)
			stack1.reverse()
			b = sol1(X, Y, stack1, stack2)
			res = a * X + b * Y
		else:
			a = sol2(X, Y, S, stack1)
			stack1.reverse()
			b = sol2(X, Y, stack1, stack2)
			res = b * X + a * Y
		return res


class Solution:

	def solve(self, X, Y, S):

		def rp(string, x, y, ans, flag):
			stack = []
			for char in string:
				if char == 'p':
					if stack and stack[-1] == 'r':
						ans[0] += y
						stack.pop()
					else:
						stack.append(char)
				else:
					stack.append(char)
			if flag:
				pr(''.join(stack), x, y, ans, False)

		def pr(string, x, y, ans, flag):
			stack = []
			for char in string:
				if char == 'r':
					if stack and stack[-1] == 'p':
						ans[0] += x
						stack.pop()
					else:
						stack.append(char)
				else:
					stack.append(char)
			if flag:
				rp(''.join(stack), x, y, ans, False)
		ans = [0]
		if X > Y:
			pr(S, X, Y, ans, True)
		else:
			rp(S, X, Y, ans, True)
		return ans[0]