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

內容目錄 隱藏

題目

給定一個字串 s 和兩個整數 x 和 y 。

刪除子字串 "ab" 獲得 x 點。
刪除子字串 "ba" 獲得 y 點。

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

解題思路

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

根據 x 和 y 的大小決定先處理哪個子字串，分數較大的先處理。
用 Stack 來處理字串，移除高優先級的子字串並計算分數。
再次使用 Stack 來處理剩餘的字串，移除低優先級的子字串並計算分數。
最後返回總得分 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
};

瀏覽量: 74