Problem Statement
Given a string S and an array of integers cost where cost[x] is the cost of deleting the x-th character in S. You will have to delete the chosen characters at the same time, (i.e after deleting a character, the cost of deleting other characters will not change). Return the minimum cost of deletions such that there are no two identical letters next to each other.
Example 1:
Input: S = "abaac", cost = [0,1,2,3,4]
Output: 2
Explanation: Delete the letter "a" with cost 2, getting the string "abac".
Example 2:
Input: S = "abcde", cost = [1,2,3,4,5]
Output: 0
Explanation: You do not need to delete any characters because there are no identical letters next to each other.
Example 3:
Input: S = "aabaa", cost = [3,2,3,4,5]
Output: 6
Explanation: Delete the second and the second last character, getting the string ("aba") with the cost of deletion = 2+4=6.
Example 4:
Input: S = "zzzz", cost = [3,4,5,6]
Output: 12
Explanation: Delete all the characters except the 'z' with the cost of 6, getting the string ("z") with the lowest cost of deletion = 3+4+5=12.
Constraints:
- S.length == cost.length
- 1 <= S.length, cost.length <= 10^5
- 1 <= cost[x] <= 10^4
- S contains only lowercase English letters ('a'-'z')
Solutions
Solution 1 : Using Arrays
def minCost(S, cost):
result=0
for i in range(len(S)-1):
if S[i]==S[i+1]:
if cost[i]<cost[i+1]:
result+=cost[i]
else:
result+=cost[i+1]
cost[i+1]=cost[i]
return result
# Driver code
if __name__ == "__main__":
S = "aabaa"
cost = [3,2,3,4,5]
print(minCost(S,cost))
Solution 2 : Using Python modules and 2 lines of code
# Importing the required modules
from itertools import groupby
from operator import itemgetter
def minCost(S, cost):
return sum(cost) - sum(max(z[1] for z in a) for _,a in groupby(zip(S, cost), key=itemgetter(0)))
# Driver code
if __name__ == "__main__":
S = "aabaa"
cost = [3,2,3,4,5]
print(minCost(S,cost))
Solution 3: Using enumerate() function and arrays
def minCost(S, cost):
maxValue=result=0
for j,key in enumerate(S):
if j-1>=0 and S[j]==S[j-1]:
result+=min(cost[j],maxValue)
maxValue=max(maxValue,cost[j])
else:
maxValue=cost[j]
return result
# Driver code
if __name__ == "__main__":
S = "aabaa"
cost = [3,2,3,4,5]
print(minCost(S,cost))
Solution 4 : Using Stack data structure
def minCost(S, cost):
if len(S) == 1:return 0
stack = []
result = 0
for j in range(len(S)-1,-1,-1):
if stack and stack[-1][0] == S[j]:
if stack[-1][1] <= cost[j]:
result += stack[-1][1]
stack.pop()
else:
result += cost[j]
continue
stack.append([S[j],cost[j]])
return result
# Driver code
if __name__ == "__main__":
S = "aabaa"
cost = [3,2,3,4,5]
print(minCost(S,cost))
Solution 5 : Using Queue data structure
import collections
def minCost(S, cost):
queue = collections.deque(S)
j = 0
previous = ""
result = 0
previousCost = 0
while queue :
current = queue.popleft()
if current == previous :
min_cost = min(previousCost, cost[j])
result += min_cost
previousCost = max(previousCost,cost[j])
else:
previous = current
previousCost = cost[j]
j += 1
return result
if __name__ == "__main__":
S = "aabaa"
cost = [3,2,3,4,5] print(minCost(S,cost))
import heapq
def minCost(S, cost):
S += '#'
cost += [float('inf')]
last_char, heap, result = '', [], 0
for j, key in enumerate(S):
if key != last_char:
while len(heap) > 1:
result += heapq.heappop(heap)
last_char, heap = key, [cost[j]]
else:
heapq.heappush(heap, cost[j])
return result # Driver code
if __name__ == "__main__":
S = "aabaa"
cost = [3,2,3,4,5] print(minCost(S,cost))
Helpful post.👍
ReplyDelete