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

Comments

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more