A. Check Whether Two Strings are Almost Equivalent (opens new window)

Count the frequency of each character.

DETAILS

bool checkAlmostEquivalent(string word1, string word2) {
        vector<int> freq(26, 0);
        for (auto ch : word1)
            freq[ch - 'a'] += 1;
        for (auto ch : word2)
            freq[ch - 'a'] -= 1;
        for (auto f : freq)
            if (f < -3 || f > 3)
                return false;
        return true;
    }

B. Walking Robot Simulation II (opens new window)

DETAILS

class Robot:
    def __init__(self, w, h):
        self.i = 0
        self.pos = [[0, 0, 'South']] + [[i, 0, 'East'] for i in range(1, w)] + \
            [[w - 1, i, 'North'] for i in range(1, h)] + \
            [[i, h - 1, 'West'] for i in range(w - 2, -1, -1)] +\
            [[0, i, 'South'] for i in range(h - 2, 0, -1)]

    def step(self, x):
        self.i += x

    def getPos(self):
        return self.pos[self.i % len(self.pos)][:2]

    def getDir(self):
        return self.pos[self.i % len(self.pos)][2] if self.i else 'East'

C. Most Beautiful Item for Each Query (opens new window)

Solution 1. Binary Search.

DETAILS

def maximumBeauty(self, A: List[List[int]], Q: List[int]) -> List[int]:
        A.sort(key = lambda x: x[0])
        res = []
        maxb = -1
        for p, b in A:
            maxb = max(maxb, b)
            if not res:
                res.append([p, maxb])
            elif res[-1][0] == p:
                res[-1][1] = max(res[-1][1], maxb)
            else:
                res.append([p, maxb])
        ans = []
        for q in Q:
            idx = bisect.bisect_right(res, [q, float('inf')])
            if idx == 0:
                ans.append(0)
            else:
                ans.append(res[idx - 1][1])
        return ans

Solution 2. Two pointers.

DETAILS

def maximumBeauty(self, A: List[List[int]], Q: List[int]) -> List[int]:
        n, idx, curb, ans = len(A), 0, 0, []
        Q = sorted([[q, i] for i, q in enumerate(Q)])
        A.sort()
        for q, i in Q:
            while idx < n and A[idx][0] <= q:
                curb = max(curb, A[idx][1])
                idx += 1
            ans.append([curb, i])
            
        return [q[0] for q in sorted(ans, key = lambda x: x[1])]

D. Maximum Number of Tasks You Can Assign (opens new window)

Binary Search.

DETAILS

from sortedcontainers import SortedList
class Solution:
    def maxTaskAssign(self, tasks, workers, pills, strength):
        tasks, workers = sorted(tasks), sorted(workers)
        def check(k):
            W = SortedList(workers[-k:])
            tries = pills
            for elem in tasks[:k][::-1]:
                place = W.bisect_left(elem)
                if place < len(W):
                    W.pop(place)
                elif tries > 0:
                    place2 = W.bisect_left(elem - strength)
                    if place2 < len(W):
                        W.pop(place2)
                        tries -= 1
                else:
                    return False
            return len(W) == 0

        beg, end = 0, min(len(workers), len(tasks)) + 1
        while beg + 1 < end:
            mid = (beg + end)//2
            if check(mid):
                beg = mid
            else:
                end = mid

        return beg