BinarySearch 0702 Delete Repeated Characters with Costs

Problem statement

https://binarysearch.com/problems/Delete-Repeated-Characters-with-Costs/

Solution

Use groupby to find groups of equal letter. Then choose the maximum corresponding value of nums and keep it. In the end calculate sum of all nums minus all we kept.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s, nums):
        arr, ans = [], 0
        for x, y in groupby(s):
            arr += [len(list(y))]
        acc = [0] + list(accumulate(arr))
        for x, y in zip(acc, acc[1:]):
            ans += max(nums[x:y])
        return sum(nums) - ans