Saturday, March 28, 2020

LeetCode 459. Repeated Substring Pattern

Question: https://leetcode.com/problems/repeated-substring-pattern/

This is the first string related question. Lots of the String algorithm questions look innocent, but when you dig into some of these questions, it takes some genius to come up with really smart and efficient algorithm. I remember learning KMP (knuth morris pratt) algorithm in class, and it really takes me a while to first understand what the algorithm is doing and then convince myself that it works. This problem is not as hard or as complicated as the KMP algorithm. The second solution is indeed quite smart.

My initial idea is that when you keep on rotating a valid repeated substring, you will eventually get back the same string. s[i:] + s[:i] is a pythonic way to rotate a string. It is easier to understand what rotating a string means. Let's say we have "abc", we shift the string to the left by one, we will have "bca" where "a" got pushed around to the end. Shift one more time, we have "cab".

class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """
        n = len(s)
        ans = False
        if n == 1:
            ans = False
        else:
            for i in range(1, n):
                if s[i] == s[0]:
                    ans = (s[i:] + s[:i]) == s
                    if ans:
                        break
        return ans

Here comes the smart algorithm:

class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """

        return s in s[1:] + s[:-1]

Why does it work? Consider the case for a valid repeated substring. Suppose the string has a repeating pattern "abc", and it repeated twice. The string is "abcabc" then when we form the string by concatenating the substring that cut off the first character and the substring that cut off the last character. We form the string "bc[abcabc]ab", we see the original string is in there as bolded. By cutting one character off the pattern, we were taking away one repeating pattern away from the original string. However, when we concatenate the substring that takes the first character away with the substring with last charater cutoff, we will get the back the original string embedded in this new string.

Thursday, March 26, 2020

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

Wednesday, March 25, 2020

LeetCode 169. Majority Element

Question: https://leetcode.com/problems/majority-element/

This is one of those popular questions that have multiple solutions. The easiest to come up with is simply iterate through the array and count the occurrences. The Efficiency of this solution is O(N). This takes 160 ms and 13.3 MB .

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """ 
        counts = {}
        n = len(nums)
        for num in nums:
            if num in counts:
                counts[num] += 1
                if counts[num] > n// 2:
                    break
            else:
                counts[num] = 1
        return num

Every time one encounters an array question, we should always think about whether sorting can help. In this case, once the array is sorted, we know that numbers of the same value are clustered, and we can increment the counter if the number under observation is the same as the previous value, and set the count back to 1 once a new value is encountered. This is O(NlogN) because of the sorting procedure. It takes 160ms and 14.2MB to run. This is rather strange, especially with the larger memory required compared to the count solution above.

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """ 
        n = len(nums)
        if n == 1:
            return nums[0]
        nums = sorted(nums)
        count = 1
        for i, num in enumerate(nums):
            if nums[i] == nums[i+1]:
                count +=1 
            else:
                count = 1
            if count > n//2:
                break
        return num

Now LeetCode's solution page has 6 different ways of solving this. I find the Boyer–Moore majority vote algorithm to be very clever and efficient. It takes only 144 ms and 13.3MB to run. By far the best solution. People can get confused about the definition of majority element. It is defined as any element that has a count greater than n//2, not the element with the largest count! For instance, let's say we have an array [7,7,5,5,1,1,7]. At first glance, it looks like 7 is the majority element. However, this is not true, there is no majority element in this array, because even 7 has only a count of 3, which is equal to 7//2=3, not exceeding n//2! So this array would not satisfy as a valid input to the question. The algorithm works exactly because of this property. The key property is this: when we encounter a tie (count=0) at index k, the majority element in [k:] will be the majority element of the original array. It takes some time to fully digest this. 

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """ 
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate