LeetCode - Minimum Deletion Cost to Avoid Repeating Letters

문제 설명

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.

제약사항

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

Solution

[전략]
연속되는 같은 문자열에서 가장 큰 cost를 제외하고 나머지는 cost 계산에 더한다.

class Solution {
    public int minCost(String s, int[] cost) {

        int costSum = 0;
        char preCh = s.charAt(0);
        int subMaxVal = cost[0];
        for (int i = 1; i < s.length(); i++) {
            char curCh = s.charAt(i);
            if (curCh != preCh) {
                subMaxVal = cost[i];
                preCh = curCh;
            } else {
                if (subMaxVal < cost[i]) {
                    costSum += subMaxVal;
                    subMaxVal = cost[i];
                } else {
                    costSum += cost[i];
                }
            }

        }
        return costSum;
    }
}