Maximum Score From Removing Substrings - Practice Coding Problems

Maximum Score From Removing Substrings - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "caba", x = 2, y = 1

› Output: 5

💡 Note: Remove the substring "ab" to get "ca", earning 2 points. Then remove "ba" is not possible. Actually, we should remove "ba" first for 1 point to get "ca", but optimal is: count pairs - we have 1 'a' before 'b' and 1 'a' after 'b', so we can form 1 "ab" pair (2 points) but no "ba" pairs. Wait, let me recalculate: "caba" - we can remove "ab" (positions 1,2) to get "ca" for 2 points, no more pairs possible. Total: 2 points.

Example 2 — Higher Y Value

$ Input: s = "aabb", x = 1, y = 2

› Output: 4

💡 Note: Since y > x, prioritize "ba" pairs. Process left to right: 'a','a','b','b'. We can form 2 "ab" pairs for 2 points, or rearrange to form 2 "ba" pairs for 4 points. Using greedy approach with y>x: we get 2 "ab" pairs total = 2×1 = 2 points. Actually optimal: we have 2 a's and 2 b's, so we can make 2 pairs. Since y>x, we want "ba" pairs, but in "aabb" we can only make "ab" pairs directly. Total: 2 points.

Example 3 — No Pairs Possible

$ Input: s = "aaa", x = 3, y = 4

› Output: 0

💡 Note: String contains only 'a' characters, so no "ab" or "ba" substrings can be formed. Total score: 0.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

String with a's and b's, point values x and y

Strategy

Remove higher-value pairs first using greedy approach

Output

Maximum total points achievable

Key Takeaway

🎯 Key Insight: Use greedy approach - always remove the more valuable substring type first to maximize total score

Asked in

G Google 25 a Amazon 18 M Microsoft 12

The key insight is to use a greedy approach: always remove the higher-value substring first. Use a stack to efficiently find and remove pairs in O(n) time. Best approach is the greedy stack method with two passes. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Stack Optimization - Single Pass	O(n)	O(n)	Use stack to remove pairs in a single pass with smart character processing
Brute Force - Try All Removal Sequences	O(2^n)	O(n)	Recursively try removing each possible "ab" or "ba" substring and return maximum score
Greedy - Remove Higher Value Pairs First	O(n)	O(n)	Always remove the more valuable substring first, then remove the less valuable ones

Stack Optimization - Single Pass — Algorithm Steps

Process each character from left to right
Use stack to match and remove pairs immediately
Prioritize higher-value pairs when both are possible

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan

Process each character from left to right

Match

Use stack to immediately match and remove high-value pairs

Count

Count remaining low-value pairs in the stack

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int solution(char* s, int x, int y) {
    int len = strlen(s);
    char* stack = malloc(len + 1);
    int top = -1;
    
    if (x >= y) {
        // Remove 'ab' pairs first
        int abPairs = 0;
        
        for (int i = 0; i < len; i++) {
            char c = s[i];
            if (top >= 0 && stack[top] == 'a' && c == 'b') {
                top--;
                abPairs++;
            } else {
                stack[++top] = c;
            }
        }
        
        // Count remaining 'ba' pairs
        int remainingA = 0;
        int baPairs = 0;
        for (int i = top; i >= 0; i--) {
            char c = stack[i];
            if (c == 'a') {
                remainingA++;
            } else if (c == 'b' && remainingA > 0) {
                remainingA--;
                baPairs++;
            }
        }
        
        free(stack);
        return abPairs * x + baPairs * y;
    } else {
        // Remove 'ba' pairs first
        int baPairs = 0;
        
        for (int i = 0; i < len; i++) {
            char c = s[i];
            if (top >= 0 && stack[top] == 'b' && c == 'a') {
                top--;
                baPairs++;
            } else {
                stack[++top] = c;
            }
        }
        
        // Count remaining 'ab' pairs
        int remainingB = 0;
        int abPairs = 0;
        for (int i = top; i >= 0; i--) {
            char c = stack[i];
            if (c == 'b') {
                remainingB++;
            } else if (c == 'a' && remainingB > 0) {
                remainingB--;
                abPairs++;
            }
        }
        
        free(stack);
        return baPairs * y + abPairs * x;
    }
}

int main() {
    char s[100001];
    int x, y;
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &x);
    scanf("%d", &y);
    
    int result = solution(s, x, y);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string, each character processed once

✓ Linear Growth

Space Complexity

O(n)

Stack can hold up to n characters in worst case

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack Optimization - Single Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler