[F 外商面試考題] deletion of the K-th letter of S costs

Leetcode 1578 Minimum Time to Make Rope Colorful

題目

給定字串 S 跟對應的 cost [Int]，找到刪除部分的 letter ，讓 S 不用會出現重複 letter 並列的最小 cost

如 S = “abccdb” and C = [0,1,2,3,4,5] 答案是 cost 是 3 的 ‘c’

思路

因為是要刪除一樣的 letter ，先判斷當前的 letter 與下一個(右邊相鄰) letter 是否一樣

一樣的話，就是要被刪除的候選者，再判斷是否當前 cost 大於下一個 cost，如果是就交換確保選定要刪除的永遠比下一個相同 letter 小

class Solution {
    func minCost(_ colors: String, _ neededTime: [Int]) -> Int {
     
        var chars = Array(colors)
        var costs = neededTime
        var ans = 0
        
        for index in (0..<(costs.count-1)) {
                        
            if chars[index] != chars[index + 1] {
                continue
            }
            
            if costs[index] > costs[index + 1] {
                costs.swapAt(index, index+1)
            }
            
            ans += costs[index]
        }
        
        return ans
    }
}

時間複雜度: O(n)

心得

班格覺得其中之的比大小 swap，原理就跟 bubble sort 一樣，只不過差異在 swap 後的就視為 delete 不用在比。