Maximum Score From Removing Substrings
MediumStringStackGreedy
Solution
export function maximumGain(s: string, x: number, y: number): number {
const [substr1, score1] = x >= y ? ['ab', x] : ['ba', y];
const [substr2, score2] = x < y ? ['ab', x] : ['ba', y];
const { result: result1, totalScore: totalScore1 } = removeSubstring(s, substr1, score1);
const { totalScore: totalScore2 } = removeSubstring(result1, substr2, score2);
return totalScore1 + totalScore2;
}
function removeSubstring(s: string, substring: string, score: number) {
let totalScore = 0;
const stack: string[] = [];
for (const char of s) {
if (stack.at(-1) === substring[0] && char === substring[1]) {
stack.pop();
totalScore += score;
} else {
stack.push(char);
}
}
return {
result: stack.join(''),
totalScore,
};
}
Complexity
- Time:
O(N)
- Spacce:
O(N)