1717. Maximum Score From Removing Substrings

[mah-shamim]

Topics: String, Stack, Greedy, Biweekly Contest 43

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 <= 105
• 1 <= x, y <= 104
• s consists of lowercase English letters.

[mah-shamim]

Here's the step-by-step implementation in PHP:

1. Determine the order of removal: It is crucial to decide the order of removing "ab" and "ba". If x > y, it is better to remove "ab" first, otherwise, remove "ba" first. This is because removing the more valuable substring first maximizes the score.

2. Use a stack to process the string: By using a stack, you can efficiently manage the removals. You push characters onto the stack and check the top of the stack to see if you can remove the desired substring.

Here's the implementation in PHP:

<?php

class Solution {

    /**
     * @param String $s
     * @param Integer $x
     * @param Integer $y
     * @return Integer
     */
    function maximumGain($s, $x, $y) {
        if ($x < $y) {
            // Swap the operations to always handle the higher value first
            $temp = $x;
            $x = $y;
            $y = $temp;
            $s = str_replace('a', 'temp', $s);
            $s = str_replace('b', 'a', $s);
            $s = str_replace('temp', 'b', $s);
        }

        // Remove 'ab' first since x >= y
        list($score1, $remainingStr) = $this->calculatePoints($s, 'ab', $x);

        // Remove 'ba' from the remaining string
        list($score2, $remainingStr) = $this->calculatePoints($remainingStr, 'ba', $y);

        return $score1 + $score2;
    }

    // Function to calculate points for the given string and operations
    function calculatePoints($s, $sub, $points) {
        $stack = [];
        $score = 0;

        foreach (str_split($s) as $char) {
            if (!empty($stack) && $char == $sub[1] && end($stack) == $sub[0]) {
                array_pop($stack);
                $score += $points;
            } else {
                $stack[] = $char;
            }
        }

        return [$score, implode('', $stack)];
    }
}

    // Remove 'ab' first since x >= y
    list($score1, $remainingStr) = calculatePoints($s, 'ab', $x);

    // Remove 'ba' from the remaining string
    list($score2, $remainingStr) = calculatePoints($remainingStr, 'ba', $y);

    return $score1 + $score2;
}

// Example usage
$s = "cdbcbbaaabab";
$x = 4;
$y = 5;
echo maximumGain($s, $x, $y);  // Output: 19

$s = "aabbaaxybbaabb";
$x = 5;
$y = 4;
echo maximumGain($s, $x, $y);  // Output: 20

?>

Explanation:

1. Initial Check: If x is less than y, we swap the values of x and y, and replace a with b and vice versa in the string to always prioritize the higher value removal.

2. Stack Processing: The calculatePoints function uses a stack to keep track of characters. When the top of the stack forms the substring to be removed (either "ab" or "ba"), it pops the top element, adds the points, and continues processing the rest of the string.

3. Remove Substrings in Order: First, the higher value substring ("ab" if x >= y) is removed, then the remaining string is processed to remove the lower value substring ("ba").

This ensures that you get the maximum possible score by prioritizing the removal of higher-value substrings first.

[basharul-siddike]

Thanks for solving the problem of "Maximum Score From Removing Substrings"

[mah-shamim]

Thanks