LeetCode 925. Long Pressed Name

Question: https://leetcode.com/problems/long-pressed-name/

As a mac user, I know lots of people had issues with the butterfly keyboard. Many people complained that when a key is hit, it can repeat itself multiple time causing great pain when typing. Now this duplicate character problem can be alleviated (to the smallest degree) with the algorithm used in this question. We are checking if a typed word is a long pressed version of the word that we intended to type. While checking is not correcting, it is still a step forward. A follow-up question will be warranted to correct words like the gramma checking software (will do an algo question on this).

The general idea is to count the number of characters in groups. A valid long pressed version of the word will the same clusters of characters as in the name. For instance, for the input name="xexe", typed= "xxeexeee", we convert these two strings into a count of the characters in the group. "xexe" becomes [1,1,1,1] corresponding to the sequence of clusters [(x,1), (e,1),(x,1), (e,1)]. Similarly, "xxeexeee" will become [2,2,1,3], corresponding to the sequence of cluster [(x,2), (e,2), (x,1),(e,3)]. Once these count sequences are formed, it is obvious that any long-typed version should have a larger count of the character than the original name.

One caveat is in the count of clusters. We are comparing the neighbor two characters to see if they are the same. We can either do i and i+1, or i-1 and i. I have picked the later. In this case, when the two characters are different s[i-1] and s[i], we know the cluster ended at i-1. Count only gets incremented when the two characters are the same. So when we append count to the array, we know we are appending the length of the cluster ended at i-1. Do remember to append count to array after we exit the loop. It is because that the last check we do is for s[n-1] and s[n-2], if they are the same, the count gets incremented, but since the loop exit there, we never reach the append statement. If they are different, then as explained above, we get the count of the cluster ended at n-2, we still need to append the count to the array. Either way, we will need to append the count to the array at the end.

class Solution(object):
    def isLongPressedName(self, name, typed):
        """
        :type name: str
        :type typed: str
        :rtype: bool
        """
        
        def char_counts(s):
            counts = []
            n = len(s)
            if len(s)>=1:
                i = 1
                count = 1
                while i < n:
                    if s[i-1] == s[i]:
                        count += 1
                    else:
                        counts.append(count)
                        count = 1
                    i += 1
                counts.append(count)
            return counts
        
        name_counts = char_counts(name)
        typed_counts = char_counts(typed)
        ans = True
        if len(name_counts) != len(typed_counts):
            ans = False
        else:
            for i, count in enumerate(typed_counts):
                if name_counts[i] > typed_counts[i]:
                    ans = False
                    break
        return ans