Falling in love with Python...

Looks like the Python "snake" bit me pretty good. I get the same vibe when I first learned C#, that feeling of simplicity, readability and completeness. Not everything is perfect though, IMO: the indentation structure reminds me of Fortran (wow), I still lack to properly define variables instead of them appearing out of the blue (with no explicit type), and I must say that the support from VS to Python is not as good as the support to C# for example (it ain't bad but not optimal).

Here is a medium-level LC problem that can be solved in O(n)-time: https://leetcode.com/problems/minimum-deletion-cost-to-avoid-repeating-letters/

1578. Minimum Deletion Cost to Avoid Repeating Letters

Medium

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.

Accepted

9,222

Submissions

15,475

Basically the gist is to do a linear pass, and any block of contiguous characters you keep track of the total cost, and the max cost, and at the end, add to the return value the total cost minus the max cost. Code is below, cheers, ACC.

def minCost(self, s, cost):
    """
    :type s: str
    :type cost: List[int]
    :rtype: int
    """

    retVal = 0
    index = 0
    while index < len(s):
        maxVal = cost[index]
        anchor = s[index]
        partialCost = cost[index]
        while index+1 < len(s) and s[index+1] == anchor:
            index += 1
            partialCost += cost[index]
            maxVal = max(maxVal, cost[index])
        partialCost -= maxVal
        retVal += partialCost
        index += 1

    return retVal