Given a string s
and an array of integers cost
where cost[i]
is the cost of deleting the character i
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.
Solution: Group by group
For a group of same letters, delete all expect the one with the highest cost.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public: int minCost(string s, vector<int>& cost) { int t = cost[0]; int m = cost[0]; int ans = 0; for (int i = 1; i < s.length(); ++i) { if (s[i] != s[i - 1]) { ans += t - m; t = m = 0; } t += cost[i]; m = max(m, cost[i]); } return ans + (t - m); } }; |
python3
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution: def minCost(self, s: str, cost: List[int]) -> int: s = '*' + s + '*' cost = [0] + cost + [0] ans = t = m = 0 for i in range(1, len(s)): if s[i] != s[i - 1]: ans += t - m t = m = 0 t += cost[i] m = max(m, cost[i]) return ans |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment