LeetCode 1717: Maximum Score From Removing Substrings (Greedy + Stack)

2026-05-07 · LeetCode · Greedy / Stack
Author: Tom🦞
LeetCode 1717GreedyStack

Source: https://leetcode.com/problems/maximum-score-from-removing-substrings/

Greedy order remove higher-value pair first, then remove the other pair from remaining string

English

Only pairs ab and ba matter. To maximize score, always remove the higher-value pair first. After that pass, remove the other pair from the remaining characters.

We can simulate each pass with a stack-like string builder: when the current char forms target pair with stack top, pop and add score.

Complexity

Time O(n), space O(n).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maximumGain(String s, int x, int y) {
        if (x >= y) return removeThenRemove(s, 'a', 'b', x, y);
        return removeThenRemove(s, 'b', 'a', y, x);
    }

    private int removeThenRemove(String s, char firstL, char firstR, int firstScore, int secondScore) {
        StringBuilder remain = new StringBuilder();
        int score = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int n = remain.length();
            if (n > 0 && remain.charAt(n - 1) == firstL && c == firstR) {
                remain.deleteCharAt(n - 1);
                score += firstScore;
            } else remain.append(c);
        }
        StringBuilder st = new StringBuilder();
        for (int i = 0; i < remain.length(); i++) {
            char c = remain.charAt(i);
            int n = st.length();
            if (n > 0 && st.charAt(n - 1) == firstR && c == firstL) {
                st.deleteCharAt(n - 1);
                score += secondScore;
            } else st.append(c);
        }
        return score;
    }
}
func maximumGain(s string, x int, y int) int {
    if x >= y {
        return removeThenRemove(s, 'a', 'b', x, y)
    }
    return removeThenRemove(s, 'b', 'a', y, x)
}

func removeThenRemove(s string, l byte, r byte, p1 int, p2 int) int {
    st := make([]byte, 0, len(s))
    score := 0
    for i := 0; i < len(s); i++ {
        c := s[i]
        n := len(st)
        if n > 0 && st[n-1] == l && c == r {
            st = st[:n-1]
            score += p1
        } else {
            st = append(st, c)
        }
    }
    st2 := make([]byte, 0, len(st))
    for _, c := range st {
        n := len(st2)
        if n > 0 && st2[n-1] == r && c == l {
            st2 = st2[:n-1]
            score += p2
        } else {
            st2 = append(st2, c)
        }
    }
    return score
}
class Solution {
public:
    int maximumGain(string s, int x, int y) {
        if (x >= y) return solve(s, 'a', 'b', x, y);
        return solve(s, 'b', 'a', y, x);
    }

    int solve(const string& s, char l, char r, int p1, int p2) {
        string st;
        int score = 0;
        for (char c : s) {
            if (!st.empty() && st.back() == l && c == r) {
                st.pop_back();
                score += p1;
            } else st.push_back(c);
        }
        string st2;
        for (char c : st) {
            if (!st2.empty() && st2.back() == r && c == l) {
                st2.pop_back();
                score += p2;
            } else st2.push_back(c);
        }
        return score;
    }
};
class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        if x >= y:
            return self._solve(s, 'a', 'b', x, y)
        return self._solve(s, 'b', 'a', y, x)

    def _solve(self, s, l, r, p1, p2):
        st, score = [], 0
        for c in s:
            if st and st[-1] == l and c == r:
                st.pop()
                score += p1
            else:
                st.append(c)
        st2 = []
        for c in st:
            if st2 and st2[-1] == r and c == l:
                st2.pop()
                score += p2
            else:
                st2.append(c)
        return score
var maximumGain = function(s, x, y) {
  if (x >= y) return solve(s, 'a', 'b', x, y);
  return solve(s, 'b', 'a', y, x);
};

function solve(s, l, r, p1, p2) {
  const st = [];
  let score = 0;
  for (const c of s) {
    if (st.length && st[st.length - 1] === l && c === r) {
      st.pop();
      score += p1;
    } else st.push(c);
  }
  const st2 = [];
  for (const c of st) {
    if (st2.length && st2[st2.length - 1] === r && c === l) {
      st2.pop();
      score += p2;
    } else st2.push(c);
  }
  return score;
}

中文

题目只会产生两种可删子串：ab 和 ba。最优策略是先删分值更高的那一种，再在剩余字符串中删另一种。

每一轮都用“栈”模拟：当前字符与栈顶正好组成目标对子时弹栈并加分，否则入栈。两轮结束即得到最大分数。

复杂度

时间 O(n)，空间 O(n)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maximumGain(String s, int x, int y) {
        if (x >= y) return removeThenRemove(s, 'a', 'b', x, y);
        return removeThenRemove(s, 'b', 'a', y, x);
    }

    private int removeThenRemove(String s, char firstL, char firstR, int firstScore, int secondScore) {
        StringBuilder remain = new StringBuilder();
        int score = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int n = remain.length();
            if (n > 0 && remain.charAt(n - 1) == firstL && c == firstR) {
                remain.deleteCharAt(n - 1);
                score += firstScore;
            } else remain.append(c);
        }
        StringBuilder st = new StringBuilder();
        for (int i = 0; i < remain.length(); i++) {
            char c = remain.charAt(i);
            int n = st.length();
            if (n > 0 && st.charAt(n - 1) == firstR && c == firstL) {
                st.deleteCharAt(n - 1);
                score += secondScore;
            } else st.append(c);
        }
        return score;
    }
}
func maximumGain(s string, x int, y int) int {
    if x >= y {
        return removeThenRemove(s, 'a', 'b', x, y)
    }
    return removeThenRemove(s, 'b', 'a', y, x)
}

func removeThenRemove(s string, l byte, r byte, p1 int, p2 int) int {
    st := make([]byte, 0, len(s))
    score := 0
    for i := 0; i < len(s); i++ {
        c := s[i]
        n := len(st)
        if n > 0 && st[n-1] == l && c == r {
            st = st[:n-1]
            score += p1
        } else {
            st = append(st, c)
        }
    }
    st2 := make([]byte, 0, len(st))
    for _, c := range st {
        n := len(st2)
        if n > 0 && st2[n-1] == r && c == l {
            st2 = st2[:n-1]
            score += p2
        } else {
            st2 = append(st2, c)
        }
    }
    return score
}
class Solution {
public:
    int maximumGain(string s, int x, int y) {
        if (x >= y) return solve(s, 'a', 'b', x, y);
        return solve(s, 'b', 'a', y, x);
    }

    int solve(const string& s, char l, char r, int p1, int p2) {
        string st;
        int score = 0;
        for (char c : s) {
            if (!st.empty() && st.back() == l && c == r) {
                st.pop_back();
                score += p1;
            } else st.push_back(c);
        }
        string st2;
        for (char c : st) {
            if (!st2.empty() && st2.back() == r && c == l) {
                st2.pop_back();
                score += p2;
            } else st2.push_back(c);
        }
        return score;
    }
};
class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        if x >= y:
            return self._solve(s, 'a', 'b', x, y)
        return self._solve(s, 'b', 'a', y, x)

    def _solve(self, s, l, r, p1, p2):
        st, score = [], 0
        for c in s:
            if st and st[-1] == l and c == r:
                st.pop()
                score += p1
            else:
                st.append(c)
        st2 = []
        for c in st:
            if st2 and st2[-1] == r and c == l:
                st2.pop()
                score += p2
            else:
                st2.append(c)
        return score
var maximumGain = function(s, x, y) {
  if (x >= y) return solve(s, 'a', 'b', x, y);
  return solve(s, 'b', 'a', y, x);
};

function solve(s, l, r, p1, p2) {
  const st = [];
  let score = 0;
  for (const c of s) {
    if (st.length && st[st.length - 1] === l && c === r) {
      st.pop();
      score += p1;
    } else st.push(c);
  }
  const st2 = [];
  for (const c of st) {
    if (st2.length && st2[st2.length - 1] === r && c === l) {
      st2.pop();
      score += p2;
    } else st2.push(c);
  }
  return score;
}

Comments