What went well: I solved first three problems relatively quickly and have working intuition on the last problem.
What did not go well:

  • problem 2 is a two pointer problem, I spent time implmenting the O(N^2) approach. This can be improlved by reason through the input size and do not settle for a inefficient solution.

  • problem 3 is a problem on trees. The algorithm I settled on computing all possible paths shows duplication paths. At the end I have to resolve to an implementation with many branch checks. To improve, I want to find a clean solution to handle such answer from the bottom up senario.

  • problem 4 is a DP problme. I came up with a 3D state representation which is not efficient enough. Missing insight is noticing the third dimension on k is not necessary and this problem is essentially longest common subsequence.

Problem 1

This is a straightforward problem.

Problem 2 1456. Maximum Number of Vowels in a Substring of Given Length

# two pointers solution
def maxVowels(self, s: str, k: int) -> int:
    vs = 'aeiou'
    if not s:
        return 0
    
    if len(s) == 1:
        if s in vs:
            return 1
        return 0
    
    cnt_count = 0
    j = 0
    ans = -math.inf
    for i in range(len(s)):
        if s[i] in vs:
            cnt_count += 1
        while j < i and i - j + 1 > k:
            if s[j] in vs:
                cnt_count -= 1
            j += 1
        ans = max(ans, cnt_count)
    return ans

# 1. collect all binary tree paths from top to bottom. 
# 2. on the collection, check if each path is valid. count all the valid ones.
def pseudoPalindromicPaths (self, root: TreeNode) -> int:
        
        def is_psudo(path):
            hist = {k:0 for k in range(10)}
            for n in path:
                hist[n] += 1
            
            odd_count = 0
            for v in hist.values():
                if v % 2 == 1:
                    odd_count += 1
            
            return odd_count <= 1
        
        
        def get_paths(root):
            if not root:
                return []
            
            if not root.left and not root.right:
                return [[root.val]]
            
            elif not root.left:
                return [ [root.val] + p for p in get_paths(root.right)]
            
            elif not root.right:
                return [ [root.val] + p for p in get_paths(root.left)]
            else:
                left = get_paths(root.left)
                right = get_paths(root.right)
                
                paths = []
                for path in left + right:
                    paths.append([root.val] + path)
                return paths
        
        count = 0
        for path in get_paths(root):
            if is_psudo(path):
                count += 1
        
        return count

# TLE Version
class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        
        n1, n2 = len(nums1), len(nums2)
        memo = {}
        self.helper(nums1, n1, nums2, n2, min(n1, n2), memo)
        
        return max(memo.values())
            
    # dp[i][j][k]: value of size k dot product from first i of nums1, and first j of nums2
    def helper(self, arr1, i, arr2, j, k, memo):
        
        if (i, j, k) in memo:
            return memo[(i, j, k)]
        
        if k == 1:
            memo[(i, j, 1)] = max(max(arr1[:i]) * max(arr2[:j]), min(arr1[:i]) * min(arr2[:j]))
            return memo[(i, j, 1)]
        
        if i == 1:
            memo[(1, j, k)] = max([arr1[0] * x for x in arr2[:j]])
            return memo[(1, j, k)]
        
        if j == 1:
            memo[(i, 1, k)] = max([arr2[0] * x for x in arr1[:i]])
            return memo[(i, 1, k)]
        
        ans = max(max(0, self.helper(arr1, i - 1, arr2, j - 1, k - 1, memo)) + arr1[i - 1] * arr2[j - 1], \
            self.helper(arr1, i - 1, arr2, j, k, memo), \
            self.helper(arr1, i, arr2, j - 1, k, memo))
        
        memo[(i, j, k)] = ans
        return ans

# The only trick is to drop a dot product if < 0.
class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        return self.helper(tuple(nums1), len(nums1), tuple(nums2), len(nums2))
    
    @functools.lru_cache(None)
    def helper(self, arr1, i, arr2, j):
        if i == 0:
            return -math.inf
        
        if j == 0:
            return -math.inf
        
        return max([max(0, self.helper(arr1, i - 1, arr2, j - 1)) + arr1[i - 1] * arr2[j - 1],\
                    self.helper(arr1, i - 1, arr2, j),\
                    self.helper(arr1, i, arr2, j - 1)])