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.
1using System;
2using System.Collections.Generic;
3
4public class MaxScore {
5 public static int MaxScoreFunc(string s, int x, int y) {
6 int score = 0;
7 Stack<char> stack = new Stack<char>();
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 the higher score patterns first
14 foreach (char c in s) {
15 if (stack.Count > 0 && stack.Peek() == first && c == second) {
16 stack.Pop();
17 score += firstPoints;
18 } else {
19 stack.Push(c);
20 }
21 }
22
23 // Second pass to remove remaining patterns
24 Stack<char> secondStack = new Stack<char>();
25 while (stack.Count > 0) {
26 char c = stack.Pop();
27 if (secondStack.Count > 0 && secondStack.Peek() == second && c == first) {
28 secondStack.Pop();
29 score += secondPoints;
30 } else {
31 secondStack.Push(c);
32 }
33 }
34
35 return score;
36 }
37
38 public static void Main(string[] args) {
39 string s = "cdbcbbaaabab";
40 int x = 4;
41 int y = 5;
42 Console.WriteLine(MaxScoreFunc(s, x, y));
43 }
44}This C# solution performs substring removal using a stack, making two passes through the string to efficiently remove the substrings with the highest score first. The stack facilitates efficient removal by maintaining the last character, checking, and updating the results accordingly.
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 Java solution employs a StringBuilder for dynamic string modification, ensuring minimal pointer movement and swift modification of input for maximum score extraction through two careful scans.