BakerHub

# A. Odd String Difference (opens new window)

Save the list of differences for each word. Find the one with the unique difference list.

DETAILS 
def oddString(self, words: List[str]) -> str:
        d = collections.defaultdict(list)
        for word in words:
            curr = []
            for i in range(len(word) - 1): 
                curr.append(ord(word[i + 1]) - ord(word[i]))
            d[tuple(curr)].append(word)

        for val in d.values():
            if len(val) == 1:
                return val[0]

# B. Words Within Two Edits of Dictionary (opens new window)

For each query, check if it has a difference no larger than 2 with any of the word in dictionary.

DETAILS 
def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
        res = []
        for query in queries:
            for word in dictionary:
                if sum(int(query[i] != word[i]) for i in range(len(word))) <= 2:
                    res.append(query)
                    break
        return res

# C. Destroy Sequential Targets (opens new window)

The targets can be destroyed by the same machine have the same remainder to space.

DETAILS 
def destroyTargets(self, nums: List[int], space: int) -> int:
        C, cand = collections.Counter([n % space for n in nums]), set()
        nums.sort()
        ma = max(C.values())
        for k, v in C.items():
            if v == ma:
                cand.add(k)
        for n in nums:
            if n % space in cand:
                return n

# D. Next Greater Element IV (opens new window)

Sorted container.

DETAILS 
from sortedcontainers import SortedList
class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        n, sl = len(nums), SortedList()
        one, two = [-1] * n, [-1] * n
        for i in range(len(nums)):
            pos,rgt = sl.bisect_left((nums[i], -100)), 0
            insert_pos = -1
            if pos == 0: 
                sl.add((nums[i], i))
                continue
            while rgt < pos:
                v, idx = sl[rgt]
                if two[idx] > -1:
                    sl.pop(rgt)
                    pos = pos - 1
                elif one[idx] > -1:
                    two[idx] = nums[i]
                    rgt = rgt + 1
                else:
                    one[idx] = nums[i]
                    rgt = rgt + 1
            sl.add((nums[i], i))
        return two

← Biweekly Contest 89 →