Maximum Score From Removing Substrings

Medium

Swiggy

0 views

Topics:

ArraysTwo PointersGreedy AlgorithmsStacks

You are given a string s and two integers x and y. You can perform two types of operations any number of times.

Remove substring "ab" and gain x points.
- For example, when removing "ab" from "cabxbae" it becomes "cxbae".
Remove substring "ba" and gain y points.
- For example, when removing "ba" from "cabxbae" it becomes "cabxe".

Return the maximum points you can gain after applying the above operations on s.

Example 1:

Input: s = "cdbcbbaaabab", x = 4, y = 5
Output: 19
Explanation:
- Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score.
- Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score.
- Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score.
- Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score.
Total score = 5 + 4 + 5 + 5 = 19.

Example 2:

Input: s = "aabbaaxybbaabb", x = 5, y = 4
Output: 20

Constraints:

1 <= s.length <= 10⁵
1 <= x, y <= 10⁴
s consists of lowercase English letters.

Try coding it in LeetCode

Maximum Score From Removing Substrings

Medium

Swiggy

0 views

Topics:

ArraysTwo PointersGreedy AlgorithmsStacks

You are given a string s and two integers x and y. You can perform two types of operations any number of times.

Remove substring "ab" and gain x points.
- For example, when removing "ab" from "cabxbae" it becomes "cxbae".
Remove substring "ba" and gain y points.
- For example, when removing "ba" from "cabxbae" it becomes "cabxe".

Return the maximum points you can gain after applying the above operations on s.

Example 1:

Input: s = "cdbcbbaaabab", x = 4, y = 5
Output: 19
Explanation:
- Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score.
- Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score.
- Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score.
- Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score.
Total score = 5 + 4 + 5 + 5 = 19.

Example 2:

Input: s = "aabbaaxybbaabb", x = 5, y = 4
Output: 20

Constraints:

1 <= s.length <= 10⁵
1 <= x, y <= 10⁴
s consists of lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can you clarify the range of values for 'x' and 'y', and the maximum length of the input string 's'?
What should I return if the string 's' does not contain either 'ab' or 'ba' substrings?
Are overlapping substrings allowed? For example, in 'abab', can I remove 'ab' to get 'ab', and then remove the remaining 'ab'?
Are there any specific character restrictions on the input string 's' beyond just 'a' and 'b'?
Is the goal to maximize the score irrespective of the order in which 'ab' and 'ba' substrings are removed, or does the order matter?

Brute Force Solution

Approach

The brute force strategy to maximize the score involves trying every possible combination of removing the substrings 'ab' and 'ba' from the given string. We explore all removal orders and keep track of the highest score we can achieve. It's like trying every single possible move in a game to see which one gives the best result.

Here's how the algorithm would work step-by-step:

Start with the original string and a score of zero.
Look for the substrings 'ab' or 'ba' in the string.
If you don't find either, you can't remove anything, so the current score is the best we can do for this arrangement.
If you find 'ab', imagine removing it. Calculate the score gained from removing 'ab'. Then repeat the entire process with the shorter string and updated score.
Also, if you find 'ba', imagine removing it. Calculate the score gained from removing 'ba'. Then repeat the entire process with this shorter string and the updated score.
Keep doing this for every possible combination of removals until there are no more 'ab' or 'ba' substrings.
For each of these removal paths, record the final score.
Once you've explored all the possible removal combinations, compare all the recorded final scores.
The highest of these scores is your maximum score.

Code Implementation

def maximum_score_from_removing_substrings(string, ab_value, ba_value):
    def solve(current_string, current_score):
        max_score = current_score

        # Find the index of 'ab' in the current string.
        ab_index = current_string.find('ab')
        if ab_index != -1:
            new_string = current_string[:ab_index] + current_string[ab_index+2:]
            new_score = current_score + ab_value
            max_score = max(max_score, solve(new_string, new_score))

        # Find the index of 'ba' in the current string.
        ba_index = current_string.find('ba')
        if ba_index != -1:
            new_string = current_string[:ba_index] + current_string[ba_index+2:]
            new_score = current_score + ba_value

            # Explore the path where 'ba' is removed.
            max_score = max(max_score, solve(new_string, new_score))

        return max_score

    # Initiate the recursive process to find the maximum score.
    return solve(string, 0)

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible combinations of removing 'ab' and 'ba' substrings. In the worst-case scenario, where the string consists of alternating 'a's and 'b's (e.g., 'abababab'), at each step, we have two choices: remove 'ab' or remove 'ba'. The depth of the recursion can be up to n/2 (where n is the length of the string). Since we explore each possible combination, the number of paths we explore grows exponentially. Therefore, the time complexity is O(2^(n/2)), which is equivalent to O(2^n).

Space Complexity

O(N^2) – The brute force solution explores all possible combinations of removing 'ab' and 'ba' substrings using recursion. In the worst-case scenario, each recursive call creates a new string that is slightly shorter than the previous one, up to N levels deep. Each recursive call's string creation could take O(N) space in the worst case. Since the recursion depth can be N, the maximum number of stack frames stored on the call stack would be N, and each frame could have a string of up to length N. Thus the space complexity is O(N * N) which simplifies to O(N^2).

Optimal Solution

Approach

The key is to greedily grab the highest possible score by prioritizing the formation of the more valuable substring first. We use a stack-like structure to efficiently track and remove characters to maximize the total score.

Here's how the algorithm would work step-by-step:

First, identify which substring gives you a higher score.
Look through the given string from left to right.
If you encounter the first character of the higher-scoring substring, put it aside.
If you then encounter the second character of that same substring, combine it with the character you set aside, remove them both from consideration, and add the corresponding score to your total.
If, instead, you encounter the first character of the lower-scoring substring, check if you already have the second character for the higher-scoring substring waiting.
If so, ignore the lower-scoring substring's character and keep waiting for the higher-scoring one to complete its pair.
If not, put this lower-scoring substring's first character aside.
Repeat the process for the lower-scoring substring and use a similar approach, where you look for the second character after seeing the first character.
By always trying to form the higher-scoring substring first, you ensure the most efficient use of available characters and maximize the overall score.

Code Implementation

def maximum_score_from_removing_substrings(string, score_xy, score_yx):
    total_score = 0
    stack = []

    if score_xy > score_yx:
        first_substring = 'xy'
        second_substring = 'yx'
        first_score = score_xy
        second_score = score_yx
    else:
        first_substring = 'yx'
        second_substring = 'xy'
        first_score = score_yx
        second_score = score_xy

    for char in string:
        stack.append(char)
        # Check if we can form the higher-scoring substring
        while (len(stack) >= 2 and 
               stack[-2] == first_substring[0] and 
               stack[-1] == first_substring[1]):

            total_score += first_score
            stack.pop()
            stack.pop()

    string = ''.join(stack)
    stack = []

    for char in string:
        stack.append(char)
        # Check if we can form the lower-scoring substring
        while (len(stack) >= 2 and
               stack[-2] == second_substring[0] and
               stack[-1] == second_substring[1]):

            # Add score and remove the substring.
            total_score += second_score
            stack.pop()
            stack.pop()

    return total_score

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string 's' of length 'n' once. Inside the loop, it performs constant-time operations such as character comparisons and stack operations (push and pop, which are O(1)). Since the number of operations is directly proportional to the length of the string, the time complexity is O(n).

Space Complexity

O(N) – The algorithm uses a stack-like structure to store characters while searching for substrings. In the worst-case scenario, the stack might hold almost all the characters of the input string if no substrings are found until the very end, leading to a space proportional to the length of the input string. Therefore, the auxiliary space used is directly related to the size of the input string, N, which represents the length of the given string. The algorithm's space complexity is O(N).

Edge Cases

Case	How to Handle
Empty string s	Return 0 immediately as no substrings can be formed.
s is null	Throw IllegalArgumentException or return 0 depending on specification.
x and y are both 0	Return 0 as no score is possible regardless of substring removal.
Only 'a' or only 'b' present in s	Return 0 as the specified substrings cannot be formed.
s contains only 'ab' or only 'ba'	Calculate the maximum number of such substrings that can be fully removed without overlapping.
Large input string s to consider time complexity	The algorithm should have a time complexity that can handle large strings efficiently, such as O(n).
x or y is negative	Handle negative scores appropriately, potentially favoring the substring with a positive score.
x and y are very large numbers causing integer overflow	Use long data type to avoid potential integer overflow when calculating the total score.