Challenge

Given a String S and and an array representing the cost of each deletion. You goal is to minimize the cost needed to remove all consecutive repetive characters.

Example 1:

"aba"
[2,3,4]
=> 0

Example 2:

"abaa"
[2,3,4,1]
=> 1

Solution 1 - Brute Force - TLE

class Solution:
    def no_consecutive_letters(self, s):

        t = ""
        for e in s:
            if e !="#":
                t += e
        for i in range(1,len(t)):
            if t[i-1] == t[i]:
                return False
        return True

    def helper(self, s, current_cost, cost, index):

        if self.no_consecutive_letters(s):
            self.min_cost = min(current_cost, self.min_cost)
            return 0
        if index > self.s_len:
            return 0

        self.helper(s[:index] + "#" +s[index+1:] , current_cost + cost[index], cost,index+1)
        self.helper(s, current_cost, cost,index+1)

        return 0
            
        
    def minCost(self, s: str, cost: List[int]) -> int:
        self.s_len = len(s)-1
        self.min_cost = float("inf")
        self.helper(s, 0, cost, 0)
        return self.min_cost

Solution 2 - Greedy

class Solution:
    
    
    def remove_n_max(self, n, cost):
        c = sorted(cost)
        res = []
        for i in range(0, n-1):
            res.append(c[i])
        return sum(res)
    
    def minCost(self, s: str, cost: List[int]) -> int:
        total = 0
        i = 0
        while i < len(s):
            arr = []
            current = 0
            in_loop = False
            tmp = []
            while i < len(s)-1 and s[i] == s[i+1]:
                arr.append(cost[i])
                in_loop = True
                current +=1
                tmp.append(s[i])
                i += 1
            if in_loop is True:
                arr.append(cost[i])                
                total += self.remove_n_max(current+1, arr)
            i += 1
        return total