Site icon May's Notes

[LeetCode] 1717. Maximum Score From Removing Substrings (JS)

LeetCode Sharing

題目

給定一個字串 s 和兩個整數 xy

傳回對 s 應用上述操作後可獲得的最大分數。

解題思路

題目要求的是分數最大值,所以要先判斷哪個子字串分比較高,若 x 大就先移除 ab,若 y 大則先移除 ba

  1. 根據 xy 的大小決定先處理哪個子字串,分數較大的先處理。
  2. 用 Stack 來處理字串,移除高優先級的子字串並計算分數。
  3. 再次使用 Stack 來處理剩餘的字串,移除低優先級的子字串並計算分數。
  4. 最後返回總得分 result

完整程式碼

/**
 * @param {string} s
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var maximumGain = function(s, x, y) {
    if (s.length === 1) return 0
    let result = 0

    // 根據 x 和 y 的大小決定處理順序
    let highPair = x > y ? 'ab' : 'ba'
    let lowPair = x > y ? 'ba' : 'ab'
    let highValue = Math.max(x, y)
    let lowValue = Math.min(x, y)
    
    // 處理高優先級的子字串
    let highStack = []
    for (let char of s) {
        if (highStack.length && highStack[highStack.length - 1] === highPair[0] && char === highPair[1]) {
            highStack.pop()
            result += highValue
        } else {
            highStack.push(char)
        }
    }
    
    // 處理低優先級的子字串
    let lowStack = []
    for (let char of highStack) {
        if (lowStack.length && lowStack[lowStack.length - 1] === lowPair[0] && char === lowPair[1]) {
            lowStack.pop()
            result += lowValue
        } else {
            lowStack.push(char)
        }
    }
    
    return result
};
Exit mobile version