Given a string s and an array of integers cost where cost[i] is the cost of deleting the ith character in s.
Return the minimum cost of deletions such that there are no two identical letters next to each other.
Notice that you will delete the chosen characters at the same time, in other words, after deleting a character, the costs of deleting other characters will not change.
 
Example 1:
Input: s = "abaac", cost = [1,2,3,4,5]
Output: 3
Explanation: Delete the letter "a" with cost 3 to get "abac" (String without two identical letters next to each other).

Example 2:
Input: s = "abc", cost = [1,2,3]
Output: 0
Explanation: You don't need to delete any character because there are no identical letters next to each other.

Example 3:
Input: s = "aabaa", cost = [1,2,3,4,1]
Output: 2
Explanation: Delete the first and the last character, getting the string ("aba").

 
Constraints:

s.length == cost.length
1 <= s.length, cost.length <= 10^5
1 <= cost[i] <= 10^4
s contains only lowercase English letters.

Difficulty: interview

Starter code:

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        

Solutions:
class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        delete_cost = 0
        last = 0
        for i in range(1, len(s)):
            if s[last] == s[i]:
                if cost[last] < cost[i]:
                    delete_cost += cost[last]
                    last = i
                else:
                    delete_cost += cost[i]
            else:
                last = i
        return delete_cost

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        n=len(s)
        idx=[]
        res = 0
        for i in range(n):
            if idx and s[i]==s[idx[-1]]:
                cost_cur = cost[i]
                cost_pre = cost[idx[-1]]
                if cost_cur>cost_pre:
                    res+=cost_pre
                    idx.pop()
                    idx.append(i)
                else:
                    res+=cost_cur
            else:
                idx.append(i)
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        ##identify all candidates to delete and their costs, then pick min?
        ## a) determine the min cost to delete for each consecutive character block.
        val = 0
        i = 0
        start = 0
        while i+1<len(s):
            if s[i]==s[i+1]:
                ##current character = same as next character
                if start == 0:
                    temp = [(i,cost[i])]
                    start = 1
                else:
                    temp.append((i, cost[i]))
            else:
                if start == 1:
                    temp.append((i,cost[i]))
                    start = 0
                    temp = sorted(temp, key = lambda x:x[1])
                    print(temp)
                    val += sum([i[1] for i in temp[:-1]])
                    
            i+=1
        
        if start ==1:
            temp.append((i,cost[i]))
            temp = sorted(temp, key = lambda x:x[1])
            val += sum([i[1] for i in temp[:-1]])
            
        return val
                    


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        s = list(s)
        sums = 0
        i = 0
        while i<= len(s)-2:
            if s[i]==s[i+1]:
                sums += min(cost[i],cost[i+1])
                cost[i+1] =max(cost[i],cost[i+1])
            i+=1
            
        return sums

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        s = list(s)
        ct = 0
        i = 0
        while i<= len(s)-2:
            if s[i]==s[i+1]:
                cos = min(cost[i],cost[i+1])
                cmax = max(cost[i],cost[i+1])
                ct+= cos
                cost[i+1] = cmax
                i+=1
            else:
                i+=1
        return ct
                
                
            
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        mcost = 0

        for i in range(0, len(s)-1):

            if s[i] == s[i+1]:

                if cost[i] < cost[i+1]:
                    mcost += cost[i]
                else:
                    mcost += cost[i+1]

                    #then swap the cost
                    temp = cost[i]
                    cost[i] = cost[i+1]
                    cost[i+1] = temp


        return mcost

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        out = 0
        for i in range(len(s)-1):
            if s[i] == s[i+1]:
                out += min(cost[i],cost[i+1])
                cost[i] = max(cost[i],cost[i+1])
                cost[i+1] = max(cost[i],cost[i+1])
        return out        

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        _min = 0
        stack = []
        for i in range(len(s)):
            if not stack:
                stack.append((s[i], i))
            else:
                t = stack[-1]
                if t[0] == s[i]:
                    if cost[i] > cost[t[1]]:
                        stack.pop()
                        _min += cost[t[1]]
                        stack.append((s[i], i))
                    else:
                        stack.pop()
                        _min += cost[i]
                        stack.append((s[i], t[1]))
                else:
                    stack.append((s[i], i))
                
        return _min

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        l, total = 0, 0
        for r in range(1,len(cost)):
            if s[r] == s[l]:
                if cost[r] > cost[l]:
                    total += cost[l]
                    l = r
                else:
                    total += cost[r]
            else:
                l = r
        return total
                
            


import sys
class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        total_cost = 0
        last = None
        cost_sum = 0
        max_cost = -sys.maxsize
        for i,v in zip(s,cost):
            if last==i:
                cost_sum+=v
                max_cost = max(max_cost,v)
            else:
                if last is not None:
                    total_cost+=(cost_sum-max_cost)
                max_cost = v
                cost_sum = v
                last = i
            # print(total_cost,max_cost,cost_sum)
        total_cost+=(cost_sum-max_cost)
        return total_cost


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        ans = prev = 0 # index of previously retained letter 
        for i in range(1, len(s)): 
            if s[prev] != s[i]: prev = i
            else: 
                ans += min(cost[prev], cost[i])
                if cost[prev] < cost[i]: prev = i
        return ans 

'''
1578. Minimum Deletion Cost to Avoid Repeating Letters.  Medium

Given a string items and an array of integers costs where costs[i]
is the costs of deleting the character i in items.

Return the minimum costs of deletions such that there are
no two identical letters next to each other.

Notice that you will delete the chosen characters at the same time,
in other words, after deleting a character, the costs of deleting
other characters will not change.

Example 1:
Input: items = \"abaac\", costs = [1,2,3,4,5]
Output: 3
Explanation: Delete the letter \"a\" with costs 3 to get \"abac\"
             (String without two identical letters next to each other).

Example 2:
Input: items = \"abc\", costs = [1,2,3]
Output: 0
Explanation: You don't need to delete any character because
             there are no identical letters next to each other.

Example 3:
Input: items = \"aabaa\", costs = [1,2,3,4,1]
Output: 2
Explanation: Delete the first and the last character,
             getting the string (\"aba\").

Constraints:
items.length == costs.length
1 <= items.length, costs.length <= 10^5
1 <= costs[i] <= 10^4
items contains only lowercase English letters.

Accepted 3,761 / 7,000 submissions.
'''
class Solution:
    def minCost(self, items: str, costs: List[int]) -> int:
        '''
        Runtime: 1160 ms, faster than 50.00% of Python3 online submissions for Minimum Deletion Cost to Avoid Repeating Letters.
        Memory Usage: 24.5 MB, less than 25.00% of Python3 online submissions for Minimum Deletion Cost to Avoid Repeating Letters.
        '''
        size = len(items)
        if size < 2:
            return 0
            
        result = 0
        prv_item = items[0]
        prv_cost = costs[0]
        max_cost = tot_cost = prv_cost
        run = False
        for item, cost in zip(items[1:], costs[1:]):
            if item == prv_item:
                run = True
                tot_cost += cost
                max_cost = max(max_cost, cost)
            else:
                if run:
                    run = False
                    result += tot_cost - max_cost
                tot_cost = max_cost = cost
            prv_item = item

        if run:
            result += tot_cost - max_cost
        return result

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        
        
        H = []
        ans = 0
        
        i = 1
        while i < len(s):
            # print(i)
            if i < len(s) and s[i] == s[i-1]:
                # print('hi')
                H = []
                heapq.heappush(H,cost[i-1])
                c = 1
                while i < len(s) and s[i]==s[i-1]:
                    heapq.heappush(H,cost[i])
                    i+=1
                    c+=1
                # print('c =',c)
                while c>1:
                    t = heapq.heappop(H)
                    ans+=t
                    c-=1
            else:
                i+=1
            H=[]
        
        return ans            
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        pre = 0
        res = 0
        for idx in range(1, len(s)):
            if s[idx] == s[pre]:
                res += min(cost[idx], cost[pre])
                print((cost[pre], cost[idx]))
            
            if s[idx] != s[pre] or cost[pre] < cost[idx]:
                pre = idx
        return res


from collections import defaultdict
class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        cache = defaultdict(lambda: [float('-inf'), 0])
        last = None
        group = 0
        for cost, char in zip(cost, s):
            if char != last:
                last = char
                group += 1
                
            cache[group][0] = max(cache[group][0], cost)
            cache[group][1] +=  cost
        total = 0
        for maxCost, sum in list(cache.values()):
            total += sum - maxCost
        return total


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        i=0
        j=1
        p=0
        while j<len(s):
            if s[i]==s[j]:
                if cost[i]<cost[j]:
                    p+=cost[i]
                    i=j
                    j+=1
                else:
                    p+=cost[j]
                    j+=1      
            else:
                i=j
                j+=1
            
        return p
                


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        s = list(s)
        ct = 0
        i = 0
        while i<= len(s)-2:
            if s[i]==s[i+1]:
                ct+= min(cost[i],cost[i+1])
                cost[i+1] =max(cost[i],cost[i+1])
                i+=1
            else:
                i+=1
        return ct
                
                
            
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        nums = [v for v in s]
        res = 0
        flag = 0
        d = collections.defaultdict(set)
        i = 1
        while i < len(nums):
            while 0 <= i < len(nums) and  nums[i] == nums[i - 1]:
                d[flag].add(i)
                d[flag].add(i - 1)
                i += 1
            flag += 1
            i += 1
            
    
        for v in d.values():
            # print(v)
            print(v)
            curr_cost = [cost[c] for c in v]
            max_val = max(curr_cost)
            res += sum(curr_cost)
            print(max_val)
            res -= max_val
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        #greedy?
        target = s[0]
        cost_list = [cost[0]]
        res = 0
        for i in range(1, len(cost)):
          if s[i] == target:
            cost_list.append(cost[i])
          else:
            if len(cost_list) >= 2:
              res += sum(cost_list) - max(cost_list)
            cost_list = [cost[i]]
            target = s[i]
        if len(cost_list) >= 2: res += sum(cost_list) - max(cost_list)
        return res
        
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        answer = 0
        start = 0
        
        for i in range(1, len(s)):
            if s[start] != s[i]:
                deletions = sorted(cost[start: i], reverse=True)

                while len(deletions) > 1:
                    answer += deletions.pop()
                
                start = i
                
        deletions = sorted(cost[start: i + 1], reverse=True)

        while len(deletions) > 1:
            answer += deletions.pop()
        
        return answer

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        c=0
        si=0
        x=1
        while x<len(s):
            if s[si]==s[x] and si<x:
                if cost[si]<=cost[x]:
                    c+=cost[si]
                    si=x
                else:
                    c+=cost[x]
            else:
                si=x
            x+=1
        # for x in range(len(s)):
        #     if len(p)!=0:
        #         if s[p[-1]]==s[x]:
        #             if cost[p[-1]]<=cost[x]:
        #                 c+=cost[p[-1]]
        #                 p.pop()
        #                 p.append(x)
        #             else:
        #                 c+=cost[x]
        #         else:
        #             p.append(x)
        #     else:
        #         p.append(x)
        return c

from collections import defaultdict
class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        i = j = 0
        ans = 0
        while j < len(s):
            while j < len(s) and s[i] == s[j]:
                j += 1
            if j-i > 1:
                ans += sum(sorted(cost[i:j])[:-1])
            i = j

        return ans

import heapq

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        it = 0
        n = len(s)
        ans = 0
        while it<n:
            if it>0 and s[it-1] == s[it]:
                h,c = [],s[it]
                heapq.heappush(h,cost[it])
                heapq.heappush(h,cost[it-1])
                it+=1
                while it<n and s[it]==c:
                    heapq.heappush(h,cost[it])
                    it+=1
                sze = len(h)
                ans += sum(heapq.nsmallest(sze-1,h))
            else:
                it+=1
                
        return ans 

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        res = 0
        array = list(s)
        i = 0
        while i <= len(array)-2:
            if array[i] == array[i+1]:
                res += min(cost[i], cost[i+1])
                cost[i+1] = max(cost[i], cost[i+1])
            i+=1
        return res


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        if len(s) == 1:
            return 0
        total = 0
        s = list(s)
        l, r = 0, 1
        while r < len(s):
            if s[l] == '':
                l += 1
            else:
                if s[l] == s[r]:
                    if cost[l] > cost[r]:
                        total += cost[r]
                        s[r] = ''
                        r += 1

                    else:
                        total += cost[l]
                        l = r
                        r += 1
                else:
                    l += 1
                    r += 1
        return total


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        ans = 0
        tmp = []
        for i in range(1,len(s)):
            if s[i]==s[i-1]:
                tmp.append(i)
                tmp.append(i-1)
            if s[i]!=s[i-1] or i==len(s)-1:
                tmp = list(set(tmp))
                x = []
                for el in tmp:
                    x.append(cost[el])
                tmp = x
                tmp.sort()
                tmp = tmp[:-1]
                #print(tmp)
                ans += sum(tmp)
                tmp = []
                
        return ans


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        c = 0
        i = 0
        l = len(cost)
        while i<l-1:
            if s[i] != s[i+1]:
                i = i+1
            else:
                ch = s[i]
                dl = 0
                for char in s[i:]:
                    if char == ch:
                        dl += 1
                    else:
                        break
                m = cost[i:i+dl]
                print(m)
                c += sum(m) - max(m)
                i += dl
        return c

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        i = 0
        delete =[]
        while i < len(s)-1:
            j = i+1
            while j < len(s):
                if s[j]!=s[i]:break
                j+=1
            if j>i+1:
                temp = [a for a in range(i, j)]
                temp2 = [x for _, x in sorted(zip(cost[i:j],temp))]
                delete += temp2[:-1]
            i=j
        delete=set(delete)
        res = 0
        for i, x in enumerate(cost):
            if i in delete:
                res+=x
        return res


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        result = previous = 0
        for i in range(1, len(s)):
            if s[previous] != s[i]:
                previous = i
            else:
                result += min(cost[previous], cost[i])
                if cost[previous] < cost[i]:
                    previous = i
        return result

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        if not s:
            return 0
        last = s[0]
        i = 0
        res = 0
        while i < len(s) - 1:
            if s[i] == s[i+1]:
                j = i + 1
                sums = cost[i]
                maxs = cost[i]
                while j <len(s) and s[j] == s[j-1]:
                    sums += cost[j]
                    maxs = max(maxs, cost[j])
                    j += 1
                    
                #print(i,j)
                res += sums - maxs
                i = j
                
            else:
                i += 1
        return res
                


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        #greedy
        target = s[0]
        cost_list = [cost[0]]
        res = 0
        for i in range(1, len(cost)):
          if s[i] == target:
            cost_list.append(cost[i])
          else:
            if len(cost_list) >= 2: res += sum(cost_list) - max(cost_list)
            cost_list = [cost[i]]
            target = s[i]
        if len(cost_list) >= 2: res += sum(cost_list) - max(cost_list)
        return res
        
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        currentCost, totalCost, maxSoFar = 0, 0, 0
        for i in range(1, len(s)):
            if s[i] == s[i-1]:
                if currentCost == 0:
                    currentCost = cost[i-1] + cost[i]
                    maxSoFar = max(cost[i-1], cost[i])
                else:
                    currentCost += cost[i]
                    maxSoFar = max(maxSoFar, cost[i])
            else:
                if currentCost != 0:
                    totalCost += (currentCost - maxSoFar)
                    currentCost = 0
        if currentCost != 0:
            totalCost += (currentCost - maxSoFar)
        return totalCost

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        mx=ans=0
        p=''
        for i,(x,c) in enumerate(zip(s,cost)):
            ans+=c
            if p!=x:
                ans-=mx
                mx=0
                p=x
            if c>mx:
                mx=c
        return ans-mx

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        total_cost = 0
        i = 0
        while i < len(s) - 1:
            if s[i] == s[i + 1]:
                j = i + 1
                while j < len(s) and s[j] == s[i]:
                    j += 1
                total_cost += sum(cost[i:j]) - max(cost[i:j])
                i = j
            else:
                i += 1
        return total_cost

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        res = 0
        
        i, n = 0, len(s)
        while i < n:
            j = i
            while j < n and s[j] == s[i]:
                j += 1
                
            if j != i + 1:
                res += sum(cost[i:j]) - max(cost[i:j])              
            
            i = j
        
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        rlist = []
        cnt = 0
        for i in range(1, len(s)):
            c = s[i]
            if c == s[i-1]:
                cnt += 1
            else:
                if cnt > 0:
                    rlist.append([i-cnt-1, i])
                cnt = 0
            if i == len(s)-1 and cnt > 0:
                rlist.append([i-cnt, i+1])
        ans = []
        for r in rlist:
            if r[1]-r[0] > 1:
                t = sorted(cost[r[0]:r[1]])
                ans.append(sum(t[:-1]))
            else:
                ans.append(min(cost[r[0]:r[1]]))
        return sum(ans)

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        ans = 0
        i = 0
        while i < len(s):
            if i + 1 < len(s) and s[i] != s[i+1]:
                # print('-', s[i], i)
                i += 1
            elif i + 1 < len(s) and s[i] == s[i+1]:
                # print('+', s[i], i)
                j = i + 1
                while j + 1 < len(s) and s[j] == s[j+1]:
                    j += 1
                j += 1
                # print('+', i, j)
                summ = 0
                maxx = float('-inf')
                for k in range(i, j):
                    summ += cost[k]
                    maxx = max(maxx, cost[k])
                ans += (summ - maxx)
                i = j
            else:
                i += 1
        return ans
            
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        
        if len(s)<=1: return 0
        
        index = 1
        to_remove = 0
        
        while index<len(s):
            if s[index]!=s[index-1]:
                index += 1
                continue
            k = index
            while k<len(s) and s[k]==s[index-1]:
                k += 1
            to_remove += (sum(cost[index-1:k]) - max(cost[index-1:k]))
            index = k
            
        return to_remove

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        
        ptr1 = 0
        ptr2 = 0
        ans = 0
        for i in range(1,len(s)):
            if s[i-1] == s[i]:
                ptr2 += 1
            else:
                print((ptr1, ptr2))
                if ptr2 > ptr1:
                    ans += sum(cost[ptr1:ptr2+1]) - max(cost[ptr1:ptr2+1])
                ptr1, ptr2 = i, i
        if ptr2 > ptr1:
            ans += sum(cost[ptr1:ptr2+1]) - max(cost[ptr1:ptr2+1])
        return ans
                


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        
        arr = []
        i = 1
        while i < len(s):
            temp = set()
            if s[i] == s[i-1]:
                while i < len(s) and s[i] == s[i-1]:
                    temp.add(i-1)
                    temp.add(i)
                    i += 1
                arr += [list(temp)]
            else:
                i+=1
        
        #print(arr)
        
        c = 0
        
        for i in arr:
            temp = [cost[x] for x in i]
            c += sum(temp) - max(temp)
        
        return c
            
        
        
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        if not s:
            return 0
        last = s[0]
        i = 0
        res = 0
        while i < len(s) - 1:
            if s[i] == s[i+1]:
                j = i + 1
                while j <len(s) and s[j] == s[j-1]:
                    j += 1
                print((i,j))
                res += sum(cost[i:j]) - max(cost[i:j])
                i = j
                
            else:
                i += 1
        return res
                


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        ans = 0
        for i in range(1, len(s)):
            if s[i] == s[i-1]:
                ans += min(cost[i], cost[i-1])
                cost[i] = max(cost[i], cost[i-1])
        return ans

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        c=0
        p=0
        for i in range(1,len(s)):
            if s[i]!=s[i-1]:
                p=i
                continue
                
            if cost[p]>cost[i]:
                c+=cost[i]
            else:
                c+=cost[p]
                p=i
                
        return c                


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        res = prev = 0 
        for i in range(1, len(s)): 
            if s[prev] != s[i]: prev = i  #
            else: 
                res += min(cost[prev], cost[i])
                if cost[prev] < cost[i]: prev = i
        return res 

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        s = list(s)
        sums = 0
        i = 0
        while i<= len(s)-2:
            if s[i]==s[i+1]:
                sums += min(cost[i],cost[i+1])
                cost[i+1] =max(cost[i],cost[i+1])
                i+=1
            else:
                i+=1
        return sums
                
                
            
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        n = len(cost)
        if n <= 1:
            return 0
        res = 0
        i = 1
        while i < n:
            if s[i] == s[i - 1]:
                j = i
                # 找到连续的一片重复字母
                while j < n and s[j] == s[j - 1]:
                    j += 1
                res += sum(cost[i - 1:j]) - max(cost[i - 1:j])
                i = j
            else:
                i += 1
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        if len(cost) < 2: return 0
        ans = 0
        r = 0
        ptr = 1
        while ptr < len(cost):
            delete = False
            while ptr < len(cost) and s[ptr] == s[r]:
                # print(ptr,r)
                delete = True
                ptr += 1
            if delete:
                ans += sum(cost[r:ptr])-max(cost[r:ptr])
                ptr -= 1
            r = ptr
            ptr += 1
            
        return ans

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        if len(s)<2:
            return 0
        i = 0
        ans=[]
        while i<len(s)-1:
            if s[i]==s[i+1]:
                su=0
                m=-1
                inside = False
                while i<len(s)-1 and s[i]==s[i+1]:
                    m = max(m,cost[i],cost[i+1])
                    print((s[i],cost[i],s[i+1],cost[i+1]))
                    su += cost[i]
                    i+=1
                    inside = True
                if inside:
                    su+=cost[i]
                    ans.append(su-m)
                #ans.append(cost[i+1])
                i+=1
                
            else:
                i+=1
        return sum(ans)
                
            
                
                
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        cur =0
        mycost = 0
        while cur < len(s)-1:
            if s[cur] == s[cur+1]:
                temp=[]
                letter = s[cur]
                while cur < len(s) and s[cur] == letter:
                    temp.append(cost[cur]) 
                    cur +=1
                mycost += sum(temp) - max(temp)
            else:
                cur+=1
                
        return mycost

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        s = list(s)
        min_cost = 0
        cur = []
        for i in range(len(s)-1):
            if s[i] == s[i+1]:
                cur.append(i)
            else:
                if len(cur)>0:
                    cur.append(i)
                    min_cost += sum([cost[x] for x in cur]) - max(
                        [cost[x] for x in cur])
                    cur = []
        if len(cur)>0:
            cur.append(len(s)-1)
            min_cost += sum([cost[x] for x in cur]) - max(
                    [cost[x] for x in cur])
        return min_cost           

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        mx=ans=0
        p=''
        for i,(x,c) in enumerate(zip(s,cost)):
            ans+=c
            if p!=x:
                ans-=mx
                mx=0
            if c>mx:
                mx=c
            p=x
        return ans-mx

class Solution:
    from collections import defaultdict
    def minCost(self, s: str, cost: List[int]) -> int:
        _dic=defaultdict(list)
        start,end=0,0
        s=s+'$'
        
        for ind in range(0,len(s)-1):
            if s[ind]==s[ind+1]:
                end+=1
            else:
                if start!=end:
                    _dic[s[ind]].append((start,end))
                start=end+1
                end+=1
        
        res=0
        
        for key in _dic:
            for tup in _dic[key]:
                res+=sum(sorted(cost[tup[0]:tup[1]+1])[:(tup[1]-tup[0])])
        
        return res
                
 


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        repeats = []
        low = 0
        high = 0
        for i in range(1, len(s)):
            if s[i] == s[low]:
                high = i
            else:
                if high - low > 0:
                    repeats.append((low, high + 1))
                low = high = i
        if high - low > 0:
                    repeats.append((low, high + 1))
        total = 0
        for low, high in repeats:
            maxVal = 0
            for i in range(low, high):
                maxVal = max(maxVal, cost[i])
                total = total + cost[i]
            total = total - maxVal
        return total

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        ans = 0
        idx = 0
        left = 0
        while idx<len(s): 
            while idx+1<len(s) and s[idx] == s[idx+1]: 
                idx += 1 
            if left<idx: 
                ans += sum(cost[left:idx+1]) - max(cost[left:idx+1])
            idx += 1
            left = idx
            # print(idx, left)
            

        return ans 

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        res, last = 0, None
        max_cost = float('-inf')
        cur_cost = 0
        for i, c in enumerate(s):
            if c == last:
                if cur_cost == 0:
                    max_cost = max(cost[i - 1], max_cost)
                    cur_cost += cost[i - 1]
                cur_cost += cost[i]
                max_cost = max(cost[i], max_cost)
            else:
                if cur_cost > 0:
                    res += cur_cost - max_cost
                    cur_cost = 0
                    max_cost = float('-inf')
            # print(i, c, last, cur_cost, max_cost)
            last = c
        if cur_cost > 0:
            res += cur_cost - max_cost
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        sums = 0
        max_cost = 0
        ans = 0
        flag = False
        
        for i in range(1,len(s)):
            if s[i] == s[i-1]:
                sums += cost[i-1]
                flag = True
                if max_cost < cost[i-1]:
                    max_cost = cost[i-1]
            else:
                if flag:
                    if max_cost < cost[i-1]:
                        max_cost = cost[i-1]
                    sums += cost[i-1]
                    ans += sums - max_cost
                    # print(ans, sums, max_cost)
                sums = 0
                flag = False
                max_cost = 0
        
        if flag:
            if max_cost < cost[-1]:
                max_cost = cost[-1]
            sums += cost[-1]
            ans += sums - max_cost
            # print(ans, sums, max_cost)
                
        return ans

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        if(len(s)<=1):
            return 0
        
        prev=0
        cost_val = 0
        for i in range(1,len(s)):
            if(s[i]==s[prev]):
                if(cost[i]<=cost[prev]):
                    cost_val+=cost[i]
                else:
                    cost_val+=cost[prev]
                    prev=i
            else:
                prev=i

        return cost_val

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        rep = []
        p1 = 0
        p2 = 1
        n = len(s)
        if n == 1:
            return 0
        while p1 < n and p2 < n:
            if s[p1] == s[p2]:
                p2 += 1
            else:
                if p2 - p1 > 1:
                    rep.append((p1, p2-1))
                    p1 = p2
                    p2 = p1 +1
                else:
                    p1 += 1
                    p2 += 1
        if p1 != n-1:
            rep.append((p1, p2-1))
        
        ans = 0
        for r in rep:
            a, b = r
            big = float('-inf')
            minus = 0
            for i in range(a, b+1):
                big = max(big, cost[i])
                minus += cost[i]
                
            ans += minus - big
        
        return ans
            
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        if not s:
            return 0
        
        res = 0
        max_idx = 0 # the idx of the max cost value in the consecutive subsequence
        for i in range(1, len(s)):
            if s[i] == s[max_idx]:
                if cost[max_idx] < cost[i]:
                    res += cost[max_idx]
                    max_idx = i
                else:
                    res += cost[i]
            else:
                max_idx = i
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        st=[]
        ans=0
        for i in range(len(s)):
            if len(st)==0:
                st.append(i)
            else:
                if s[i]==s[st[-1]]:
                    if cost[st[-1]]<cost[i]:
                        ans+=cost[st[-1]]
                        st.pop()
                        st.append(i)
                    else:
                        ans+=cost[i]
                else:
                    st.append(i)
        return ans

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        #greedy
        target = s[0]
        track_max = cost[0]
        curr_sum = cost[0]
        res = 0
        for i in range(1, len(cost)):
          if s[i] == target:
            track_max = max(track_max, cost[i])
            curr_sum += cost[i]
          else:
            if curr_sum != cost[i-1]: res += (curr_sum) - track_max
            track_max = cost[i]
            curr_sum = cost[i]
            target = s[i]
        if curr_sum != cost[i-1]: res += (curr_sum) - track_max
        return res
        
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        _min = 0
        for i in range(len(s)-1):
            if s[i] == s[i+1]:
                _min += min(cost[i], cost[i+1]) 
                if cost[i] >= cost[i+1]:
                    cost[i+1] = cost[i]
        return _min

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        res = 0
        if len(s) < 2: return res
        first, second = 0, 1
        while second < len(s):
            if s[first] == s[second]:
                if cost[first] <= cost[second]:
                    res += cost[first]
                    first = second
                    second += 1
                else:
                    res += cost[second]
                    second += 1
            else:
                first = second
                second += 1
        return res


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        total=0
        for i in range(1,len(s)):
            if s[i-1]==s[i]:
                total+=min(cost[i-1],cost[i])
                cost[i] = max(cost[i-1],cost[i])
        return total

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        def find_cost(start, end):
            a = cost[start:end+1]
            a.sort()
            return sum(a[:-1])
        
        res = 0
        if len(s) == 1:
            return res
        
        i = 1
        start = -1
        while i < len(s):
            if s[i-1] == s[i] and start < 0:
                start = i-1
            if s[i] != s[i-1] and start >= 0:
                res += find_cost(start, i-1)
                start = -1
            i += 1
        if start >= 0:
            res += find_cost(start, len(s)-1)       
        
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        if len(s) == 1:
            return 0
        temp = []
        j=0
        for i in range(len(s)):
            if i == len(s)-1:
                if s[i]==s[j]:
                    temp.append([j,i+1])
                else:
                    if (i-j)>1:
                        temp.append([j,i])
            else:
                if s[j]!=s[i]:
                    if (i-j) >1:
                        temp.append([j,i])
                    j=i
        res = 0     
        for i,j in temp:
            new = cost[i:j]
            val = max(new)
            p=0
            while p < len(new):
                if new[p] == val:
                    new.pop(p)
                    break
                p+=1
            res+=sum(new)
        return res


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        if len(s) == 1:
            return 0
        pre_c = s[0]
        pre_cost_max = cost[0]
        count = 0
        for c, _cost in zip(s[1:], cost[1:]):
            if c == pre_c:
                count += min(pre_cost_max, _cost)
                pre_cost_max = max(pre_cost_max, _cost)
            else:
                pre_c = c
                pre_cost_max = _cost
        return count

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        length = 1
        start, end = 0, 0
        result = 0
        for i in range(len(s)-1):
            if s[i] == s[i+1]:
                if length == 1:
                    start = i
                length += 1
            else:
                if length > 1:
                    end = i
                    sm = sum(cost[start:end+1])
                    mx = max(cost[start:end+1])
                    result += sm-mx
                start = 0
                end = 0
                length = 1
        if length > 1:
            end = len(s)-1
            sm = sum(cost[start:end+1])
            mx = max(cost[start:end+1])
            result += sm-mx
        return result

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        to_delete = []
        i = 0
        while i < len(s):
            j = i + 1
            flag = False
            while j < len(s) and s[j] == s[i]:
                j += 1
                flag = True
            if flag:
                to_delete.append((i, j))
            i = j
        ans = 0
        # print(to_delete)
        for interval in to_delete:
            cos = sorted(cost[interval[0] : interval[1]])
            l = interval[1] - interval[0] - 1
            index = 0
            for _ in range(l):
                ans += cos[index]
                index += 1
        return ans

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        # identify consecutive characters
        consecutive_log = []
        consecutive_tuple = [-1,-1,-1]
        previous_e = -1
        for i, e in enumerate(s):
            if e != previous_e:
                consecutive_log.append(consecutive_tuple)
                consecutive_tuple = [e, i, i]
                previous_e = e
            else:
                consecutive_tuple[2]=i
                previous_e=e
        consecutive_log.append(consecutive_tuple)
        # print(consecutive_log)
        
        total_cost = 0
        for log in consecutive_log:
            if log[1] != log[2]:
                selected_costs = cost[log[1]:log[2]+1]
                max_cost = max(selected_costs)
                selected_costs.remove(max_cost)
                total_cost += sum(selected_costs)
        return total_cost
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        stack = []
        ans = 0
        for i,c in enumerate(s):
            if stack and s[stack[-1]] == c:
                if cost[stack[-1]] < cost[i]:
                    ans += cost[stack[-1]]
                    stack.pop()
                    stack.append(i)
                else:
                    ans += cost[i]
            else:
                stack.append(i)
        return ans
                


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        n = len(s)
        minCost = 0
        
        left = right = 0
        while right < n:
            while right < n and s[right] == s[left]:
                right += 1
                
            if right == left + 1:
                left += 1
            else: 
                minCost += sum(cost[left:right]) - max(cost[left:right])
                left = right

        return minCost

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        l,r=0,1
        total=0
        dels =0
        for i in range(1,len(s)):
            if s[i-1]==s[i]:
                total+=min(cost[i-1],cost[i])
                cost[i] = max(cost[i-1],cost[i])
        return total

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        res = 0

        n = len(s)
        # while i < n:
        # if i  + 1 < n and s[i] == s[i + 1]:
        stack = []
        # for i, c in enumerate(s):
        i = 0
        while i < n:
            c = s[i]
            if stack and s[stack[-1]] == c:
                j = stack.pop()
                prev_cost = cost[j]
                if prev_cost < cost[i]:
                    stack.append(i)
                else:
                    stack.append(j)
                res += min(prev_cost, cost[i])
                i += 1
            else:
                stack.append(i)
                i += 1
            # print(stack, i, c, res)
            # if not stack:
            #     stack.append(i)
            #     i += 1
            # else:
            #     i += 1
        # print(res)
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        if len(s) == 0: return 0
        
        prev = 0
        min_cost = 0
        for c, group in itertools.groupby(list(s)):
            group = list(group)
            left = prev
            right = left + len(group) - 1
            prev = right + 1
            if len(group) == 1: continue
            
            x = max(cost[left: right + 1])
            total = sum(cost[left: right + 1])
            min_cost += total - x 
            
        return min_cost

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        ans, n, prev = 0, len(s), 0
        for i in range(1, n):
            if s[i] == s[i - 1]:
                if cost[i] > cost[prev]:
                    ans += cost[prev]
                    prev = i
                else: ans += cost[i]
            else: prev = i
        return ans


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        # O(n), greedy or stack
        
        res = 0
        i = 0
        while i < len(s)-1:
            temp = i
            while i < len(s)-1 and s[i] == s[i+1]:
                i += 1
            if temp < i:
                res += sum(cost[temp:i+1]) - max(cost[temp:i+1])
            i += 1
        return res
                


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        
        res = 0
        prev = ''
        pool = []
        
        for c, v in zip(s + ' ', cost + [0]):
            if c != prev:
                if len(pool) > 1:
                    res += sum(pool) - max(pool)
                prev = c
                pool = [v]
            else:
                pool.append(v)
        
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        prv = 0
        
        res = 0
        for i in range(1, len(s)):
            if s[i] != s[i - 1]:
                if i - prv > 1:
                    mc = cost[prv]
                    for j in range(prv, i):
                        res += cost[j]
                        if cost[j] > mc:
                            mc = cost[j]
                    res -= mc
                prv = i
        
        if len(s) - prv > 1:
            mc = cost[prv]
            for j in range(prv, len(s)):
                res += cost[j]
                if cost[j] > mc:
                    mc = cost[j]
            res -= mc
        
        return res
                


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        st = []
        st.append((s[0], 0))
        res = 0
        n = len(s)
        for i in range(1, n):
            if st[-1][0] == s[i]:
                x = st[-1][1]
                if(cost[x] >= cost[i]):
                    res += cost[i]
                else:
                    res += cost[x]
                    st.pop()
                    st.append((s[i], i))
            else:
                st.append((s[i], i))
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        output=0
        s = list(s)
        i=0
        while i  < (len(s)-1):
            if s[i] ==s[i+1]:
                
                if i == len(s)-2:
                    output += min(cost[i],cost[i+1])
                else:
                    j=i+2
                    
                    while s[i] ==s[j] and j < len(s)-1:
                        #print(j)
                        j+=1
                    
                    print(cost[i:j])
                   
                    
                    if s[-1]!=s[-2]:
                        output =output + sum(cost[i:j]) - max(cost[i:j])
                    
                    elif j == len(s)-1:
                        output =output + sum(cost[i:j+1]) - max(cost[i:j+1])
                    else:
                        output =output + sum(cost[i:j]) - max(cost[i:j])
                    i=j-1
            i+=1
                
        return output

from typing import List
class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        s = list(s)
        idx = [i for i in range(len(s))]
        dic = dict(zip(idx, cost))
        w = 0
        cost = 0
        for k in range(len(s)-1, 0, -1):
            w = k - 1    
            if s[k] == s[w]:
                kCost = dic[k]
                wCost = dic[w]
                if kCost <= wCost:
                    cost += kCost
                    del s[k]
                else:
                    cost += wCost
                    del s[w]
                    dic[w] = dic[k]
        s = ''.join(s)
        return cost

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        n = len(s)
        res = 0
        i = j = 0
        while j < n:
            i = j
            while j + 1 < n and s[j] == s[j + 1]:
                j += 1
            res += sum(cost[i:j+1]) - max(cost[i:j+1] or [0])
            # print(i, j, cost[i:j+1])
            j += 1
        # print(s,cost, res)
        # print()
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        ss = list(s)
        tot_cost = 0
        i = 0
        while i < len(ss) - 1:
            if ss[i] == ss[i+1]:
                start_i = i
                end_i = i+1
                while end_i < len(ss) - 1 and ss[end_i] == ss[end_i + 1]:
                    end_i += 1
                dup_sum = sum(cost[start_i:end_i+1])
                dup_max = max(cost[start_i:end_i+1])
                tot_cost += dup_sum - dup_max
                i = end_i
            i += 1
        
        return tot_cost

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        res = 0
        
        if len(s) <= 1:
            return 0
        
        i = 0
        while i < len(s)-1:
            j = i
            costs = []
            isCost = False
            while j <= len(s)-2 and s[j+1] == s[i]:
                isCost = True
                costs.append(cost[j])
                j += 1
            if isCost:
                costs.append(cost[j])
            res += sum(sorted(costs, reverse=True)[1:])
            i = j
            i += 1
                
                
        return res
                


class Solution:
    def minCost(self, S: str, cost: List[int]) -> int:
        def checkStr(s):
            i=1
            out = []
            while i<len(s):
                j=i
                out1 = set([])
                if s[j]==s[j-1]:
                    while j<len(s) and s[j]==s[j-1]:
                        out1.add(j-1)
                        out1.add(j)
                        j+=1
                    out.append(list(out1))
                    i=j
                else:
                    i+=1
            return out
        
        cst = 0
        s = list(S)
        indexes = checkStr(s)
        # print (indexes)
        i=0
        while i<len(indexes):
            curr = indexes[i]
            costs = list(map(lambda x:cost[x], curr))
            # print (costs)
            cst+=sum(costs)-max(costs)
            i+=1
        return cst

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        ma,res,total = 0,0,0
        i = 0
        while i < len(s)-1:
            start = i
            while i < len(s)-1 and s[i+1] == s[i]:   #哪个在and前很重要
                i +=1
            end = i
            if start == end:
                i += 1
            else:
                for j in range(start, end+1):
                    ma = max(ma, cost[j])
                    total += cost[j]
                res += total-ma
                ma = 0
                total = 0
        return res
                
        
#         for i in range(len(s)-1):
#             if s[i+1] == s[i]:
#                 temp = min(cost[i],cost[i+1])
#                 res += temp
                
#         return res


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        ans, pos = 0, 0
        
        for _, v in itertools.groupby(s):
            v = list(v)
            if len(v) > 1:
                to_sort = []
                for x in range(len(v)):
                    to_sort.append(cost[pos])
                    pos += 1
                ans += sum(sorted(to_sort)[:-1])
            else:
                pos += 1
            
        return ans

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        res = 0
        stack = []
        idx = 0
        while idx < len(s):
            while idx < len(s) - 1 and s[idx] == s[idx+1]:
                stack.append(cost[idx])
                idx += 1
            if idx > 0 and s[idx] == s[idx-1]:
                stack.append(cost[idx])
            if stack:
                res += (sum(stack) - max(stack))
                stack = []
            idx += 1
        return res

class Solution:
    def minCost(self, s: str, cost) -> int:
        l = 0
        ans = 0
        while l < len(s):
            r = l + 1
            if r < len(s) and s[r] == s[l]:
                tmp_cost = cost[l]
                max_cost = cost[l]
                while r < len(s) and s[r] == s[l]:
                    max_cost = max(max_cost, cost[r])
                    tmp_cost += cost[r]
                    r += 1
                ans += tmp_cost - max_cost
            l = r
        return ans


from heapq import nsmallest

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        if len(s) < 2:
             return 0
        left, right = 0, 1
        res = 0
        window = dict()
        while right < len(s):
            if s[right] != s[left]:
                right += 1
                left += 1
                continue
            print(left)
            while right < len(s) and s[right] == s[left]:
                right += 1
            res += sum(nsmallest(right - left - 1, cost[left:right]))
            left = right 
            right += 1
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        import heapq
        prev = ''
        prices = []
        count = 0
        ans = 0
        for char, cost in zip(s, cost):
            if prev == char:
                heapq.heappush(prices, cost)
                count += 1
                continue
            else:
                for _ in range(count):
                    ans += heapq.heappop(prices)
                count = 0
                prev = char
                prices = [cost]
        if count != 0:
            for _ in range(count):
                    ans += heapq.heappop(prices)
        return ans

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        if len(s)<=1: return 0
        res = 0
        start = 0
        while True:
            if start>=len(s):
                break
            temp = start+1
            for i in range(temp, len(s)):
                if s[i]!=s[start]:
                    start += 1
                else:
                    break
            if start==len(s)-1:
                break
            end = start+2
            while end<len(s):
                if s[end]==s[start]:
                    end += 1
                else:
                    break
            res += (sum(cost[start:end]) - max(cost[start:end]))
            start = end
        return res
        '''
        start = -1
        for i in range(1, len(s)):
            if s[i]==s[i-1]:
                start = i-1
                break
        if start==-1: return 0
        end = start+2
        SUM = cost[start]+cost[start+1]
        MAX = max(cost[start], cost[start+1])
        while end<len(s):
            if s[end]==s[start]:
                SUM += cost[end]
                MAX = max(cost[end], MAX)
                end += 1
            else:
                break
        res += (SUM-MAX)
        return res+self.minCost(s[end:], cost[end:])
        '''

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        s = list(s)
        sums = 0
        i = 0
        while i<= len(s)-2:
            if s[i]==s[i+1]:
                sums += min(cost[i],cost[i+1])
                cost[i+1] =max(cost[i],cost[i+1])
            i+=1
        return sums
                
                
            
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        answer = 0
        start = 0
        
        for i in range(1, len(s)):
            if s[start] != s[i]:
                deletions = sorted(cost[start : i], reverse=True)

                while len(deletions) > 1:
                    answer += deletions.pop()
                
                start = i
                
        deletions = sorted(cost[start : len(s)], reverse=True)

        while len(deletions) > 1:
            answer += deletions.pop()
        
        return answer

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        
        output = []
        idx = 0
        while idx < len(s):
            char = s[idx]
            newIdx = idx+1
            arr = [idx]
            while newIdx < len(s) and s[newIdx] == s[idx]:
                arr.append(newIdx)
                newIdx += 1
            
            idx = newIdx              
            output.append(arr)
            
        totalCost = 0
        for newArr in output:
            if len(newArr) > 1:
                costArr = []
                for eachElem in newArr:
                    costArr.append(cost[eachElem])
                    
                sortedArr = sorted(costArr, reverse=True)
                
                totalCost += sum(sortedArr[1:])
        
        return totalCost
        


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        def num(s):
            return ord(s)-ord('a')
        dp=[0,0]
        n=len(s)
        # val=[-1]*26
        C=1
        for i in range(1,n):
            if s[i]==s[i-1]:
                if C==1:
                    max_c=max(cost[i-1],cost[i])
                    sum_c=dp[-1]+cost[i-1]+cost[i]
                else:
                    max_c=max(max_c,cost[i])
                    sum_c+=cost[i]
                c = sum_c-max_c
                C+=1
                dp.append(c)
            else:
                C=1
                dp.append(dp[-1])
        return dp[-1]

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        
        left, right = 0, 1
        costSum = 0
        while right < len(s):
            
            if s[left] == s[right]:
                while right < len(s) and s[left] == s[right]:
                    right += 1
                tmp = cost[left:right]
                maxIndex = tmp.index(max(tmp))
                for i in range(len(tmp)):
                    if i != maxIndex:
                        costSum += tmp[i] 
                left = right
                right += 1
            else:
                left += 1
                right += 1
        return costSum


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        
        def getNextIdx(idx):
            curr = s[idx]
            for j, ch in enumerate(s[idx+1:]):
                if ch != curr:
                    return j+idx+1
            return len(s)

        i = 0
        
        sol = 0
        
        while i < len(s):
            next_i = getNextIdx(i)
            if i < len(s)-1 and s[i] != s[i+1]:
                i += 1
            else:
                curr = s[i]
                max_cost_idx = i
                for xx in range(i+1, min(next_i, len(s))):
                    if cost[xx] > cost[max_cost_idx]:
                        max_cost_idx = xx
                for idx in range(i, min(next_i, len(s))):
                    # print(idx)
                    if idx != max_cost_idx:
                        sol += cost[idx]
                i = next_i
        return sol


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        s=list(s)
        ret=0
        i=1
        while i<len(s):
            if s[i]==s[i-1]:
                ret+=min(cost[i],cost[i-1])
                if cost[i]<cost[i-1]:
                    
                    cost[i],cost[i-1]=cost[i-1],cost[i]
            i+=1
        return ret

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        
        if len(s) == 0:
            return 0
        if len(s) == 1:
            return 0

        
        @lru_cache(maxsize = None)
        def dp(n):
            
            if n == 0:
                return (0, 0)
            
            last = dp(n-1) #(val, lastword_index)
            ans = 0
            lastans = last[0]
            last_index = last[1]
            
            next_index = 0
            
            if s[last_index] == s[n]:
                if cost[last_index] <= cost[n]:
                    ans = lastans + cost[last_index]
                    next_index = n
                    #print(n, last_index, ans)
                else:
                    ans = lastans + cost[n]
                    next_index = last_index
                    #print(n, n, ans)
            else:
                ans = lastans
                next_index = n
                
            return (ans, next_index)
        
        return dp(len(s)-1)[0]

from functools import reduce
class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        t = 0
        n = len(s)
        if n <= 1:
            return 0
        ins = s
        s = n
        p = '?'
        e = -1
        for i,l in enumerate(ins):
            if p == l:
                if s == n:
                    s = i-1
            else:
                p = l
                if s != n:
                    #only ones before are problematic
                    t += reduce(lambda a,b:a+b,cost[s:i],0) - max(cost[s:i])
                    s = n
        if s != n:
            t += reduce(lambda a,b:a+b,cost[s:],0) - max(cost[s:])
        return t
                


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        pre = None
        val = 0
        ans = 0
        for e, v in zip(s, cost):
            if pre == e:
                ans += min(v, val)
                val = max(v, val)
            else:
                pre, val = e, v
        return ans

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        total = 0
        for i in range(1,len(s)):
            if s[i] == s[i-1]:
                total += min(cost[i],cost[i-1])
                cost[i] = max(cost[i],cost[i-1])
        return total

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        to_delete = []
        for i in range(len(s)):
            if i > 0 and s[i] == s[i - 1] or i < len(s) - 1 and s[i] == s[i + 1]:
                to_delete.append(i)
        
        groups, temp, prev = [], [], -1
        for i in range(len(to_delete)):
            if prev == -1:
                prev = to_delete[i]
                temp.append(to_delete[i])
            else:
                if i == len(to_delete) - 1:
                    temp.append(to_delete[i])
                    groups.append(temp[:])
                else:
                    if to_delete[i + 1] - to_delete[i] > 1 or s[to_delete[i + 1]] != s[to_delete[i]]:
                        temp.append(to_delete[i])
                        groups.append(temp[:])
                        prev = -1
                        temp = []
                    else:
                        temp.append(to_delete[i])

        ans = 0
        for group in groups:
            total = 0
            highest = 0
            for index in group:
                total += cost[index]
                highest = max(highest, cost[index])
            ans += total - highest
            
        return ans

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        answer=0; i=0;
        while i<len(s)-1:
            if s[i]==s[i+1]:
                #input();
                sumCost = cost[i]; maxCost = cost[i];
                j=i+1;
                while(j<len(s)-1 and s[j]==s[j+1]):
                    sumCost+=cost[j];
                    maxCost = max(maxCost, cost[j]);
                    j+=1;
                if s[j]==s[i]:
                    sumCost+=cost[j];
                    maxCost = max(maxCost, cost[j]);
                #print('i=',i,'j=',j,'sumCost=', sumCost,'maxCost=', maxCost)
                answer += sumCost-maxCost;
                i=j+1
            else:
                i+=1;
        return answer;

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
      prev = None
      min_cost = 0
      pq = []
      
      for char, c in zip(s, cost):
        if not prev:
          prev = char
          heapq.heappush(pq, c)
        elif prev != char:
          prev = char
          while len(pq) > 1:
            min_cost += heapq.heappop(pq)
          pq = [c]
        else:
          heapq.heappush(pq, c)
          
      while len(pq) > 1:
        min_cost += heapq.heappop(pq)
        
      return min_cost


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        s = list(s)
        if len(s) < 2:
            return 0
        if len(s) == len(set(s)):
            return 0
        total = 0
        while True:
            i = 0                
            deleted = False
            for _, group in itertools.groupby(s):
                group = list(group)
                if len(group) > 1:
                    idx_max, max_cost = -1, -1
                    for j, c in enumerate(cost[i:i + len(group)]):
                        if c == None:
                            continue
                        if c > max_cost:
                            max_cost = c
                            idx_max = i + j
                    subtotal = 0
                    for j in range(i, i + len(group)):
                        if j == idx_max:
                            continue
                        subtotal += cost[j]
                        cost[j] = None
                        s[j] = None
                    total += subtotal
                    deleted = True
                i += len(group)
            if deleted:
                s = [c for c in s if c != None]
                cost = [c for c in cost if c != None]
            else:
                break
        return total

def has_two_consecutive_chars(s: str) -> bool:
    for i in range(1, len(s)):
        if s[i - 1] == s[i]:
            return True
    return False


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        res = 0
        i = 1
        temp = cost[0]
        while i < len(cost):
            if s[i-1] == s[i]:
                res += min(temp, cost[i])
                temp = max(temp, cost[i])
            else:
                temp = cost[i]
            i += 1
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        n = len(s)
        
        memo = {}
        def f(prev, i):
            if i == n:
                return 0
            
            if (prev, i) in memo:
                return memo[(prev, i)]
            
            if s[i] == prev:
                # No choice, we have to delete s[i]
                memo[(prev, i)] = cost[i] + f(s[i], i + 1)
            elif i + 1 >= n or s[i] != s[i+1]:
                # The next character is the not the same as s[i], no need to delete
                memo[(prev, i)] = f(s[i], i + 1)
            else:
                # The next character exists (i + 1 < n) and it is the same as s[i].
                # We may choose to delete s[i] or not delete s[i], return the min cost
                # of two choices
                memo[(prev, i)] = min(cost[i] + f(prev, i + 1), f(s[i], i + 1))
            
            return memo[(prev, i)]
    
        return f(None, 0)
                      
            
            
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        # print(\"===\")
        repeating=[]
        last=None
        ans=0
        for i,c in enumerate(s):
            # print(\"processing\",c)
            if c!=last:
                last=c
                if len(repeating)>1:
                    cost_win=cost[i-len(repeating):i]
                    spent = sum(cost_win)-max(cost_win)
                    # print(spent)
                    ans+=spent
                
                repeating= [c]
            
            else:
                repeating.append(c)
                
        if len(repeating)>1:
            cost_win=cost[len(s)-len(repeating):]
            spent = sum(cost_win)-max(cost_win)
            # print(spent)
            ans+=spent
        return ans

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        stack = []
        
        res = 0
        for i in range(len(cost)):
            if not stack or s[stack[-1]] != s[i]:
                stack.append(i)
            else:
                if stack and s[stack[-1]] == s[i]:
                    idx = stack.pop()
                    if cost[idx] >= cost[i]:
                        res += cost[i]
                        stack.append(idx)
                    else:
                        res += cost[idx]
                        stack.append(i)
        return res
                
                


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        s = s+'#'
        totalcost = 0
        idx = 1
        while idx<len(s):
            if s[idx] == s[idx-1]:
                start = idx-1
                end = idx
                idx +=1
                
                while idx<len(s):
                    
                    if s[idx]!=s[idx-1]:
                        end = idx-1
                        break
                    else:
                        idx+=1
                 
                
                
                print((start,end))
                totalcost +=sum(cost[start:end+1])-max(cost[start:end+1])
            else:
                idx +=1
        return totalcost
            
            
                
                    
            
              
                    


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        mcost=0
        i=0
        c=0
        j=0
        while(i<len(s)):
            j=i
            while(i<len(s) and s[j]==s[i]):
                i+=1
                c+=1
            if(c!=1):
                mcost+=sum(cost[j:i])-max(cost[j:i])
            c=0
        return mcost

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        s += '~'
        def dedup(exp:List[int]) -> int:
            return sum(exp) - max(exp)
        
        res = 0
        current = []
        for i in range(len(s)-1):
            if s[i+1] == s[i]:
                if len(current) == 0:
                    current.append(cost[i])
                current.append(cost[i+1])
            else:
                if len(current) > 1:
                    res += dedup(current)
                current = []
        
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        s=list(s)
        c=0
        i=0
        while(i<len(s)-1):
            # start=i
            st=0
            end=0
            if(s[i]==s[i+1]):
                st=i
                while(i<len(s)-1 and s[i]==s[i+1]):
                        end=i+1
                        i+=1
                    
                print((st,end))
                c+=sum(cost[st:end+1])-max(cost[st:end+1])
                print(c)
            else:
                i+=1
        return c
                


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        prev_idx = None
        count = 0
        for ii in range(1, len(s)):
            b = s[ii]
            if prev_idx is None:
                prev_idx = ii - 1
            a = s[prev_idx]
            if a == b:
                cost_a = cost[prev_idx]
                cost_b = cost[ii]
                count += min(cost_a, cost_b)
                prev_idx = max([cost_a, prev_idx], [cost_b, ii])[1]
            else:
                prev_idx = None
        return count

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        temp=[]
        t=[]
        i=0
        while i<len(s)-1:
            if s[i]==s[i+1]:
                t.append(i)
            while i<len(s)-1 and s[i]==s[i+1]:
                t.append(i+1)
                i+=1
            if len(t)>0:
                temp.append(t)
                t=[]
            i+=1
        else:
            if len(t)>0:
                temp.append(t)
                t=[]
        print(temp)
        ans=0
        for i in temp:
            tt=-max(cost[min(i):max(i)+1])
            tt+=sum(cost[min(i):max(i)+1])
            ans+=tt
        return ans


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        i=0
        ans=0
        while i<len(s):
            if i<len(s)-1 and s[i]==s[i+1]:
                n=0
                t=i
                temp=s[i]
                while i<len(s) and s[i]==temp:
                    i+=1
                    n+=1
                #print(n, s, cost, cost[t:t+n], sum(cost[t:t+n]), max(cost[t:t+n]))
                ans+=(sum(cost[t:t+n])-max(cost[t:t+n]))
            else:
                i+=1
        return ans


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        
        @lru_cache
        def f(s, i):
            if i == len(s):
                return 0
            j = i
            while j+1 < len(s) and s[j] == s[j+1]:
                j += 1
                
            if j == i:
                a = 0
            else:
                xx  = sorted([cost[k] for k in range(i, j+1)])
                a = sum(xx[:-1])
            
            return a + f(s, j+1)
        
        
        return f(s, 0)


import heapq
class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        i = 1
        h = []
        summ = 0
        while i < len(s):
            if(s[i]==s[i-1]):
                while(i<len(s) and s[i]==s[i-1]):
                    heapq.heappush(h,cost[i-1])
                    i+=1
                heapq.heappush(h,cost[i-1])
                while len(h)>1:
                    summ += heapq.heappop(h)
                heapq.heappop(h)
            else:
                i+=1
        return summ

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        cur_max = cur_cost = 0
        total = 0
        for i in range(1, len(s)):
            if s[i] == s[i-1]:
                if cur_cost == 0:
                    cur_cost = cost[i] + cost[i-1]
                    cur_max = max(cost[i], cost[i-1])
                else:
                    cur_cost += cost[i]
                    cur_max = max(cur_max, cost[i])
            elif cur_cost != 0:
                    total += cur_cost - cur_max
                    cur_cost = cur_max = 0

        if cur_cost != 0:
            total += cur_cost - cur_max

        return total

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        result = 0
        p1 = 0
        while p1 < len(s) - 1:
            if s[p1] == s[p1+1]:
                p2 = p1
                totalSum, maxCost = cost[p2], cost[p2]
                while p2 < len(s)-1 and s[p2] == s[p2+1]:
                    p2 += 1
                    totalSum += cost[p2]
                    maxCost = max(maxCost, cost[p2])
                result += totalSum-maxCost
                p1 = p2+1
            else:
                p1 += 1
                
        return result
                    


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        n = len(s)
        def getnextidx(k):
            for l in range(k+1, n):
                if s[k] != s[l]:
                    return l
            return n
            
        i = 0
        cost_used = 0
        while i < n:
            j = getnextidx(i)
            if j - i > 1:
                cost_used += sum(cost[i:j]) - max(cost[i:j])
            i = j
            
        return cost_used

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        
        res = 0
        i = 1
        N = len(s)
        
        while i < N:
            if s[i] == s[i-1]:
                maxcost = cost[i-1]
                totalcost = cost[i-1]
                while i < N and s[i] == s[i-1]:
                    totalcost += cost[i]
                    maxcost = max(maxcost, cost[i])
                    i += 1
                    
                print(totalcost, maxcost)
                res += (totalcost - maxcost)
                
            i += 1
            
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        s += '~'
        def dedup(exp:List[int]):
            return sum(exp) - max(exp)
        
        res = 0
        current = []
        for i in range(len(s)-1):
            if s[i+1] == s[i]:
                if len(current) == 0:
                    current.append(cost[i])
                current.append(cost[i+1])
            if s[i+1] != s[i]:
                if len(current) > 1:
                    res += dedup(current)
                current = []
        
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        cumu_cost = 0
        max_cost = None
        
        prev_char = None
        prev_cost = None
        
        result = 0
        
        for char, v in zip(s, cost):
            
            if prev_char and prev_char == char:
                if max_cost is None:
                    cumu_cost += v + prev_cost
                    max_cost = max(v, prev_cost)
                else:
                    cumu_cost += v
                    max_cost = max(max_cost, max(v, prev_cost))
                
            elif prev_char and prev_char != char and max_cost is not None:
                
                result += cumu_cost - max_cost
                cumu_cost = 0
                max_cost = None
                
                
                
        
            prev_char = char
            prev_cost = v
        
        if prev_char and max_cost is not None:
            result += cumu_cost - max_cost
        
        return result

        



class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        last_char = ''
        start = 0
        ans = 0
        s += '_'
        cost.append(0)
        
        for i,c in enumerate(s):
            
            if c != last_char:
                if i- start>1:
                    ans += sum(cost[start: i]) - max(cost[start: i])
                last_char = c
                start = i
                
        return ans
            
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:

        i = 0
        tot = 0
        while i < len(s) - 1:
            if s[i] == s[i + 1]:
                start = i
                while i < len(s) - 1 and s[i] == s[i + 1]:
                    i += 1
                mx = 0
                for c in cost[start: i + 1]:
                    tot += c
                    mx = max(mx, c)
                tot -= mx
            i += 1
        return tot


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        head_idx, tail_idx = 0, 1
        total_cost = 0
        
        while tail_idx < len(s):
            if s[head_idx] == s[tail_idx]:
                if cost[head_idx] < cost[tail_idx]:
                    total_cost += cost[head_idx]
                    head_idx, tail_idx = tail_idx, tail_idx+1
                else:
                    total_cost += cost[tail_idx]
                    tail_idx += 1
            else:
                head_idx, tail_idx = tail_idx, tail_idx+1
                
        return total_cost
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        c=0
      
        for i in range(len(s)):
            if i-1>=0 and s[i-1]==s[i]:
                continue
            k=i
            while k<len(s) and s[k]==s[i]:
                k+=1
            if k>i+1:
                print(i)
                a=sum(cost[i:k])-max(cost[i:k])
                c+=a
        return c

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        ans=[]


        i=0

        while i<len(s):
            count=0
            for j in range(i+1,len(s)):
                if s[j]!=s[i]:
                    break
                else:
                    count+=1
            if count>0:
                ans.append((i,i+count))
            i=j
            if i==len(s)-1:
                break

        res=0

        i=(3,5)

        for i in ans:
            k=sorted(cost[i[0]:i[1]+1])
            res=res+sum(k[0:i[1]-i[0]])
        
        return res




class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
    
        s += '~'
    
        def dedup(exp:List[int]):
            return sum(exp) - max(exp)
        
        res = 0
        i = 0
        current = []
        while i+1 < len(s) :
            if s[i+1] == s[i]:
                if len(current) == 0:
                    current.append(cost[i])
                current.append(cost[i+1])
            if s[i+1] != s[i]:
                if len(current) > 1:
                    res += dedup(current)
                current = []
            i+=1
            
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        i = 1
        current_cost = cost[0]
        max_cost = cost[0]
        ans = 0
        while i < len(cost):
            while i < len(cost) and s[i] == s[i-1]:
                current_cost += cost[i]
                max_cost = max(max_cost, cost[i])
                i += 1
                
            ans += current_cost - max_cost
            
            if i < len(cost):
                current_cost = cost[i]
                max_cost = cost[i]
            
            i += 1
            
        return ans

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        i=0
        res=0
        j = 1
        while j<len(s):
            if s[i]==s[j]:
                res+=min(cost[i],cost[j])
                cost[j]=max(cost[i],cost[j])
            i+=1
            j+=1
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        if len(s) < 2:
            return 0
        f = 0
        i = 0
        s = list(s)
        while i < len(s) - 1:
            v1 = s[i]
            v2 = s[i+1]
            
            if v1 == v2:
                
                c1 = cost[i]
                c2 = cost[i+1]
                
                #print(v1,c1,c2,i)
                
                if c1 < c2:
                    f += c1
                else:
                    f += c2
                    cost[i+1] = c1
            i += 1
        
        return f

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        out = 0
        for i in range(len(s)-1):
            if s[i] == s[i+1]:
                out += min(cost[i],cost[i+1])
                cost[i+1] = max(cost[i],cost[i+1])
        return out        

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
    
        s += '~'
    
        def dedup(exp:List[int]):
            print(exp)
            return sum(exp) - max(exp)
        
        res = 0
        i = 0
        current = []
        while i+1 < len(s) :
            if s[i+1] == s[i]:
                if len(current) == 0:
                    current.append(cost[i])
                current.append(cost[i+1])
                
            if s[i+1] != s[i]:
                if len(current) > 1:
                    res += dedup(current)
                current = []
            i+=1
            
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        last_char = ''
        start = 0
        ans = 0
        s += '_'
        cost.append(0)
        
        for i,c in enumerate(s):
            
            if c != last_char:
                if i- start>1:
                    print(ans)
                    ans += sum(cost[start: i]) - max(cost[start: i])
                last_char = c
                start = i
                
        return ans
            
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        inner_array = []
        outer_array = []
        consecutive = False
        for i, val in enumerate(zip(s, cost)):
            if i == len(cost) - 1:
                break
            else:
                char = val[0]
                c = val[1]
                if char == s[i + 1]:
                    if consecutive:
                        inner_array.append(cost[i+1])
                    else:
                        inner_array.append(c)
                        inner_array.append(cost[i+1])
                        consecutive = True
                    if i == len(cost) - 2:
                        outer_array.append(inner_array)
                else:
                    consecutive = False
                    if inner_array:
                        outer_array.append(inner_array)
                        inner_array = []

        res = 0
        for i in outer_array:
            res += sum(sorted(i)[:-1])

        return res
                

            
                


class Solution:
        
    def minCost(self, s: str, cost: List[int]) -> int:
        result = 0
        low = 0
        
        while low < len(cost) - 1:
            high = low + 1
            while high < len(cost) and s[high] == s[low]:
                high += 1
            
            if high - low > 1:
                a, ma = 0, float('-inf')
                for i in range(low, high):
                    a += cost[i]
                    ma = max(ma, cost[i])
                result += a - ma
            low = high
        return result

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        
        n = len(s)
        if n ==1:
            return 0
        start = 0
        end = 1
        splits = []
        while end < n:
            while end<n and s[end]==s[start]:
                end+=1
            splits.append((start,end-1))
            start = end
        
        answer = 0
        for start,end in splits:
            if start == end:
                continue
            else:
                maxi = 0
                costsum=0
                for i in range(start,end+1):
                    maxi = max(maxi,cost[i])
                    costsum += cost[i]
                costsum -= maxi
                answer += costsum
        return answer
                    
                    
                    
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        res = 0
        for k, g in itertools.groupby(zip(s, cost), key=lambda p: p[0]):
            g = list(g)
            if len(g) > 1:
                costs = [t[1] for t in g]
                res += sum(costs) - max(costs)
        return res

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        fee = max_cost = 0
        for i, cst in enumerate(cost):
            if i > 0 and s[i] != s[i - 1]:
                max_cost = 0
            fee += min(cst, max_cost)
            max_cost = max(cst, max_cost)
        return fee    

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        current_char = 'A'
        current_max = 0
        answer = 0
        for i, c in enumerate(cost):
            if s[i] == current_char:
                if current_max < c:
                    answer += current_max
                    current_max = c
                else:
                    answer += c
            else:
                current_char = s[i]
                current_max = c
        return answer

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        
        s = list(s)
        v = 0
        i = 0
        while i < len(s)-1:
            if s[i] == s[i+1]:
                v += min(cost[i],cost[i+1])   
                cost[i+1] = max(cost[i],cost[i+1])
            i += 1
            
        return v

class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        s = list(s)
        sums = 0
        i = 0
        while i<= len(s)-2:
            if s[i]==s[i+1]:
                sums += min(cost[i],cost[i+1])
                cost[i+1] =max(cost[i],cost[i+1])
            i+=1
            
        return sums
            


class Solution:
    def minCost(self, s: str, cost: List[int]) -> int:
        s = s + ' '
        out = 0
        deleted = set()
        start = 0
        l = len(s)
        while True:
            prev = '='
            to_delete = []
            for i in range(start, l):
                if i in deleted:
                    continue
                if s[i] == prev:
                    to_delete.append((cost[prev_i], prev_i))
                elif to_delete:
                    to_delete.append((cost[prev_i], prev_i))
                    break
                prev = s[i]
                prev_i = i
            else:
                break
            start = prev_i
            
            to_delete.sort(reverse=True)
            for i in range(1, len(to_delete)):
                out += to_delete[i][0]
                deleted.add(to_delete[i][1])
        return out
            
            
        


class Solution:
    def minCost(self, S: str, B: List[int]) -> int:
        def if_continues_char(ind):
            return S[ind] == S[ind+1]

        def consecutive_char(ind):
            consecutive_cost = B[ind]
            min_cost = B[ind]
            while ind < len(S) - 1 and S[ind] == S[ind+1]:
                ind += 1
                consecutive_cost += B[ind]
                min_cost = max(min_cost, B[ind])
            return ind + 1, consecutive_cost - min_cost

        if not S or not B:
            return 0
        i, cost = 0, 0
        while i < len(S) - 1:
            if if_continues_char(i):
                i, del_cost = consecutive_char(i)
                cost += del_cost
            else:
                i += 1
        return cost