1717. Maximum Score From Removing Substrings
Approach
Greedy stack — remove higher-scoring pair first, then lower-scoring pair in second pass.
Key Techniques
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
Stacks support LIFO (last-in, first-out) operations in O(1). Key patterns: balanced parentheses, next greater element (monotonic stack), function call simulation, and undo/redo. A monotonic stack maintains a strictly increasing or decreasing order to answer range queries efficiently.
// Approach: Greedy stack — remove higher-scoring pair first, then lower-scoring pair in second pass.
// Time: O(n) Space: O(n)
public class Solution
{
public int MaximumGain(string s, int x, int y)
{
return x > y ? Gain(s, "ab", x, "ba", y) : Gain(s, "ba", y, "ab", x);
}
private int Gain(string s, string sub1, int point1, string sub2, int point2)
{
int points = 0;
var st1 = new Stack<char>();
// First pass: remove sub1 patterns
foreach (char c in s)
{
if (st1.Count > 0 && st1.Peek() == sub1[0] && c == sub1[1])
{
st1.Pop();
points += point1;
}
else
st1.Push(c);
}
// Convert stack to string to preserve correct order
var remaining = new char[st1.Count];
for (int i = remaining.Length - 1; i >= 0; i--)
{
remaining[i] = st1.Pop();
}
// Second pass: remove sub2 patterns from remaining characters
var st2 = new Stack<char>();
foreach (char c in remaining)
{
if (st2.Count > 0 && st2.Peek() == sub2[0] && c == sub2[1])
{
st2.Pop();
points += point2;
}
else
st2.Push(c);
}
return points;
}
}