Problem Breakdown
Restatement: We are given a string of characters and an associated cost array for deleting each character at that index. Our goal is to remove the minimum total cost such that no two identical characters appear consecutively in the resulting sequence. The deletion operation is simultaneous; removing one character does not shift indices or change costs, but it effectively removes adjacency constraints between neighbors if they were separated by a deleted item (though for this specific problem logic, we treat contiguous blocks of identical characters independently).
Inputs:
s: A string containing lowercase English letters.cost: An integer array wherecost[i]corresponds to the deletion cost ofs[i].
Outputs:
- Integer: The minimum total deletion cost required.
Implicit Constraints & Edge Cases:
- Adjacency Definition: Only immediate neighbors in the original string matter for adjacency checks, but since we delete characters “at once”, a contiguous block of identical characters (e.g.,
aaa) must be reduced to exactly one character instance to satisfy the condition. We cannot keep two adjacent ‘a’s within that original segment without deleting all intermediate ones, which is impossible if they are already adjacent in input. - Empty/Single Input: Constraints state length . If a string has no duplicates (e.g.,
abc), cost is 0. - Overflow: Costs can sum up to , which fits within standard integer types, but Python handles arbitrary precision integers automatically so overflow isn’t a concern here.
Intuition
Brute Force Approach: A naive solution might try every possible subset of characters to delete and check validity. This would involve iterating through subsets (where is string length). With , this is computationally infeasible ().
Key Insight:
The problem can be decomposed into independent subproblems. Consider a contiguous segment of identical characters, e.g., aaabbaa. The first three ‘a’s form one group; the two ‘b’s are different and break adjacency constraints between groups; the last two ‘a’s form another group.
Within any single contiguous block of identical characters (e.g., indices to where all chars match), we must reduce this sequence so that no two remain adjacent. Since they are already adjacent in the input, keeping more than one would violate the rule immediately unless we delete everything between them—but there is nothing “between” them inside a contiguous block of identical characters. Therefore, for any maximal contiguous run of identical characters (), we must keep exactly one instance and delete all others to satisfy the condition (or rather, if we kept two from that specific original segment without deleting intermediates, they would be adjacent).
To minimize cost within such a block:
- We calculate the sum of costs for all characters in this contiguous run.
- To keep one character “for free” and delete the rest, we should retain the character with the highest deletion cost (since keeping it saves us from paying that high price).
- The minimum cost to resolve a block is:
Sum(costs_in_block) - Max(costs_in_block).
If (a single unique char surrounded by different chars), Sum = Cost, Max = Cost. Difference is 0. This logic holds universally for all blocks of length .
Optimal Approach: We iterate through the string once to identify these contiguous groups and accumulate their resolution costs.
Complexity Analysis
- Time Complexity: where is
s.length. We traverse the array exactly once, performing constant-time operations (addition, comparison) per character. - Space Complexity: . We only use a few variables to track current group sums and maximum costs regardless of input size.
Solution
def minDeletionCost(s: str, cost: list[int]) -> int:
if not s or len(cost) == 0:
return 0
total_cost = 0
# Initialize tracking variables for the current contiguous group of identical characters
prev_char = s[0]
current_sum = cost[0]
current_max = cost[0]
# Iterate starting from the second character to detect changes in adjacent chars
for i in range(1, len(s)):
if s[i] == prev_char:
# Same character as previous; extend current group
current_sum += cost[i]
current_max = max(current_max, cost[i])
else:
# Different character encountered; the previous group has ended.
# Add the deletion cost for that finished group to total (Sum - Max).
total_cost += (current_sum - current_max)
# Reset tracking variables for the new character starting a fresh group
prev_char = s[i]
current_sum = cost[i]
current_max = cost[i]
# After loop finishes, we must account for the final contiguous group that ended at len(s)-1
total_cost += (current_sum - current_max)
return total_cost
Edge Cases Handled
- Single Character String: The loop
range(1, 1)does not execute. Code adds(cost[0] - cost[0])which is 0 tototal_cost. Correctly returns 0 as no deletions needed. - No Duplicates (e.g., “abc”): Every character triggers the
elsebranch immediately after initialization or resets variables such thatcurrent_sum == current_max, adding 0 cost each time. Returns 0. - All Identical Characters: The loop runs, accumulating sum and max for all characters until end of string. Final addition computes
(Sum - Max). This correctly represents deleting everyone except the most expensive one in a contiguous block. - Large Costs/Lengths: Python handles large integers natively; logic remains regardless of magnitude within standard constraints ().