Sponsored
Sponsored
In this approach, we prioritize removing the substring with a higher score first. We utilize a stack to efficiently traverse and remove substrings from the string. Given two substrings 'ab' and 'ba', and their scores x and y, we decide which to remove first based on the higher score. The stack helps in processing the string in a single pass, adding character by character and checking for the target substring ending each time.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), for the stack used in substring removal.
1#include <iostream>
2#include <string>
3#include <stack>
4
5int maxScore(std::string s, int x, int y) {
6 int score = 0;
7 std::stack<char> stk;
8 char first = x > y ? 'a' : 'b';
9 char second = x > y ? 'b' : 'a';
10 int firstPoints = x > y ? x : y;
11 int secondPoints = x > y ? y : x;
12
13 // Remove higher score patterns first
14 for (char c : s) {
15 if (!stk.empty() && stk.top() == first && c == second) {
16 stk.pop();
17 score += firstPoints;
18 } else {
19 stk.push(c);
20 }
21 }
22
23 // Second pass to remove remaining lower score patterns
24 std::string remaining;
25 while (!stk.empty()) {
26 remaining += stk.top();
27 stk.pop();
28 }
29 std::reverse(remaining.begin(), remaining.end());
30
31 for (char c : remaining) {
32 if (!stk.empty() && stk.top() == second && c == first) {
33 stk.pop();
34 score += secondPoints;
35 } else {
36 stk.push(c);
37 }
38 }
39
40 return score;
41}
42
43int main() {
44 std::string s = "cdbcbbaaabab";
45 int x = 4;
46 int y = 5;
47 std::cout << maxScore(s, x, y) << std::endl;
48 return 0;
49}This C++ solution functions similarly to the C solution with the utilization of a stack to maximize score. It demonstrates efficient parsing and handling using the stack data structure to find and remove target substrings.
The Two-Pointer approach leverages two pointers to parse through the string and eliminate substrings optimally. By managing two scanning points, determining which pattern to remove can be executed with minimal operations, optimizing score calculation effectively.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), due to stack arrays used to manage character tracking.
1
This C solution uses two pointers combined with a simulated stack to efficiently parse and optimize substring removal by maximizing the scores at each step through linear traversal.