Problem of The Day: Maximum Score From Removing Substrings
Problem Statement
Brute Force - TLE
class Solution:
def maximumGain(self, s: str, x: int, y: int) -> int:
@cache
def dfs(i, curr):
if i > len(curr):
return 0
res = 0
for j in range(i, len(curr)):
if curr[j:j+2] == 'ab':
res = max(res, dfs(0, curr[:j] + curr[j+2:]) + x)
elif curr[j:j+2] == 'ba':
res = max(res, dfs(0, curr[:j] + curr[j+2:]) + y)
return res
return dfs(0, s)
Intuition
When I first looked at this problem, my initial thought was to find a way to maximize the score by removing the highest-scoring substrings first. This involves using a stack to efficiently manage the removal process, as stacks allow us to easily access and remove the most recent characters.
Approach
My approach involves two main phases:
- Primary Removal: I remove the highest-scoring substring (
ab
orba
depending on the values ofx
andy
) from the string using a stack. - Secondary Removal: After the primary pass, I remove the second highest-scoring substring from the remaining string using another stack.
To determine the order of removal based on the scores x
and y
, I use a dictionary called action_score
.
Complexity
- Time complexity: The time complexity is \(O(n)\) because I traverse the string twice (once for each pass).
- Space complexity: The space complexity is \(O(n)\) due to the use of stacks to hold characters during processing.
Code
class Solution:
def maximumGain(self, s: str, x: int, y: int) -> int:
action_score = defaultdict()
if x > y:
action_score['first'] = ['ba', x]
action_score['second'] = ['ba', y]
else:
action_score['second'] = ['ab', x]
action_score['first'] = ['ab', y]
s1 = list(s)
res = 0
s2 = []
while s1:
s2.append(s1.pop())
if len(s2) < 2:
continue
if ''.join(s2[-2:]) == action_score['first'][0]:
res += action_score['first'][1]
s2.pop()
s2.pop()
while s2:
s1.append(s2.pop())
if len(s1) < 2:
continue
if ''.join(s1[-2:]) == action_score['second'][0]:
res += action_score['second'][1]
s1.pop()
s1.pop()
return res
Editorial
class Solution:
def maximumGain(self, s: str, x: int, y: int) -> int:
total_score = 0
high_priority_pair = "ab" if x > y else "ba"
low_priority_pair = "ba" if high_priority_pair == "ab" else "ab"
# First pass: remove high priority pair
string_after_first_pass = self.remove_substring(s, high_priority_pair)
removed_pairs_count = (len(s) - len(string_after_first_pass)) // 2
# Calculate score from first pass
total_score += removed_pairs_count * max(x, y)
# Second pass: remove low priority pair
string_after_second_pass = self.remove_substring(
string_after_first_pass, low_priority_pair
)
removed_pairs_count = (
len(string_after_first_pass) - len(string_after_second_pass)
) // 2
# Calculate score from second pass
total_score += removed_pairs_count * min(x, y)
return total_score
def remove_substring(self, input: str, target_pair: str) -> str:
char_stack = []
# Iterate through each character in the input string
for current_char in input:
# Check if current character forms the target pair with the top of the stack
if (
current_char == target_pair[1]
and char_stack
and char_stack[-1] == target_pair[0]
):
char_stack.pop() # Remove the matching character from the stack
else:
char_stack.append(current_char)
# Reconstruct the remaining string after removing target pairs
return "".join(char_stack)