A. Counting Words With a Given Prefix (opens new window)

Startswith.

DETAILS

int prefixCount(vector<string>& W, string pref) {
        int ans = 0;
        for (auto w : W) 
            if (w.rfind(pref, 0) == 0)
                ans += 1;
        return ans;
    }

public int prefixCount(String[] W, String pref) {
        int ans = 0;
        for (String w : W)
            if (w.startsWith(pref))
                ans += 1;
        return ans;
    }

def prefixCount(self, W: List[str], pref: str) -> int:
        return len([w for w in W if w.startswith(pref)])

B. Minimum Number of Steps to Make Two Strings Anagram II (opens new window)

Counter. If S has num more character ch than T, fill T by num*ch, and vise versa.

DETAILS

def minSteps(self, S: str, T: str) -> int:
        cs, ct = collections.Counter(S), collections.Counter(T)
        ans = 0
        for ch in cs.keys():
            if cs[ch] > ct.get(ch, 0):
                ans += cs[ch] - ct.get(ch, 0)
                ct[ch] = cs[ch]
        for ch in ct.keys():
            if ct[ch] > cs.get(ch, 0):
                ans += ct[ch] - cs.get(ch, 0)
                cs[ch] = ct[ch]
        return ans

C. Minimum Time to Complete Trips (opens new window)

Binary Search.

• If time x is enough, search for a shorter time.
• Otherwise, search for a longer time.

DETAILS

def minimumTime(self, T: List[int], trips: int) -> int:
        l, r = min(T), max(T) * trips + 1
        while l < r:
            m = (l + r) // 2
            cur = 0
            for t in T:
                cur += m // t
            if cur < trips:
                l = m + 1
            else:
                r = m
        return l 

D. Minimum Time to Finish the Race (opens new window)

DP

DETAILS

def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
        go_straight = [inf for _ in range(19)]
        for f, r in tires:
            tot = cur = f
            go_straight[1] = min(go_straight[1], tot)
            for i in range(2, 19):
                cur *= r
                tot += cur
                if tot > 2e5: 
                    break
                go_straight[i] = min(go_straight[i], tot)

        DP = [0 for _ in range(numLaps + 1)]
        for i in range(1, numLaps + 1):
            DP[i] = go_straight[i] if i < 19 else inf
            for j in range(1, i//2 + 1):
                DP[i] = min(DP[i], DP[j] + changeTime + DP[i - j])
        return DP[-1]