LeetCode 1717: Maximum Score From Removing Substrings Solution

Master LeetCode problem 1717 (Maximum Score From Removing Substrings), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1717. Maximum Score From Removing Substrings

Medium

String Stack Greedy

Problem Explanation

Explanation:

To solve this problem, we can use a greedy approach. We repeatedly remove "ab" and "ba" substrings from the given string until no more such substrings can be removed. During each removal, we keep track of the points gained and return the maximum score.

Initialize a variable score to 0.
While there are "ab" or "ba" substrings in the string:
- Find the index of the first occurrence of "ab" or "ba".
- Remove the found substring and add x or y points to the score accordingly.
Return the final score.

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(1)

Solution Code

class Solution {
    public int maximumGain(String s, int x, int y) {
        StringBuilder sb = new StringBuilder(s);
        int score = 0;
        
        while (true) {
            int idx1 = sb.indexOf("ab");
            int idx2 = sb.indexOf("ba");
            
            if (idx1 == -1 && idx2 == -1) {
                break;
            }
            
            if (idx1 != -1 && (idx2 == -1 || idx1 < idx2)) {
                sb.delete(idx1, idx1 + 2);
                score += x;
            } else {
                sb.delete(idx2, idx2 + 2);
                score += y;
            }
        }
        
        return score;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1717 (Maximum Score From Removing Substrings)?

This page provides optimized solutions for LeetCode problem 1717 (Maximum Score From Removing Substrings) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1717 (Maximum Score From Removing Substrings)?

The time complexity for LeetCode 1717 (Maximum Score From Removing Substrings) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1717 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1717 in Java, C++, or Python.

Back to LeetCode Solutions