A. Greatest English Letter in Upper and Lower Case (opens new window)

Check if both the upper case and lower case of a character appears in the string and return the largest one if exists.

DETAILS

def greatestLetter(self, s: str) -> str:
        freq = [0] * 26
        for ch in s:
            if ch.isupper():
                freq[ord(ch) - ord('A')] |= 2
            else:
                freq[ord(ch) - ord('a')] |= 1
        ans = -1
        for i in range(25, -1, -1):
            if freq[i] == 3:
                return chr(ord('A') + i)
        return ""

B. Sum of Numbers With Units Digit K (opens new window)

Start from k and increment by k each time, if the remainder of the sum when divided by 10 equals that of A, return the number of increments. If we have already added by 10*k and still haven't get the same remainder, return -1.

DETAILS

def minimumNumbers(self, A: int, k: int) -> int:
        if A == 0: return 0
        if k % 2 == 0 and A % 2 != 0: return -1

        n, cur = 0, 0
        while True:
            n += 1
            cur += k
            if cur % 10 == A % 10:
                break
            if n > 9:
                return -1

        return -1 if n * k > A else n

C. Longest Binary Subsequence Less Than or Equal to K (opens new window)

Greedy. Assume the length of k in binary representation is nk, start from the right side of s, apparently the binary number made by the first nk-1 characters is smaller than k. Then we take all the rest 0s all the way to the leftmost side, calculate the total number of 0s collected plus nk-1.

DETAILS

def longestSubsequence(self, s: str, k: int) -> int:
        ns = len(s)
        N = bin(k)[2:]
        nk = len(N)
        ans = nk if s[-nk:] <= N else nk - 1
        for i in range(ns - nk):
            if s[i] == '0':
                ans += 1
        return min(ans, ns)

D. Selling Pieces of Wood (opens new window)

Please refer to This LC Discussion (opens new window) for my solutions in English.

DP

DETAILS

def sellingWood(self, m: int, n: int, P: List[List[int]]) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for r, c, p in P:
            dp[r][c] = p
            
        for r in range(1, m + 1):
            for c in range(1, n + 1):
                # Find all the possible first cut:
                for nc in range(1, c // 2 + 1): 
                    dp[r][c] = max(dp[r][c], dp[r][nc] + dp[r][c - nc])
                for nr in range(1, r // 2 + 1):
                    dp[r][c] = max(dp[r][c], dp[nr][c] + dp[r - nr][c])
                    
        return dp[m][n]