A. Strong Password Checker II (opens new window)

Check if the input string satisfies every constrain.

DETAILS

def strongPasswordCheckerII(self, password: str) -> bool:
        if len(password) < 8: 
            return False
        ss, n, checker = "!@#$%^&*()-+", len(password), 0
        for i in range(n - 1):
            if password[i] == password[i + 1]:
                return False
        for ch in password:
            if ch.isdigit():
                checker += 1
                break
        for ch in password:
            if ch.islower():
                checker += 1
                break
        for ch in password:
            if ch.isupper():
                checker += 1
                break
        for ch in password:
            if ch in ss:
                checker += 1
                break   
        return checker == 4

B. Successful Pairs of Spells and Potions (opens new window)

Binary Search, sort potions, for each spell, we find the smallest succeed potion, then all the potions with no less strength work as well.

DETAILS

def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()
        n = len(potions)
        return [n - bisect.bisect_left(potions, math.ceil(success/s)) for s in spells]

C. Match Substring After Replacement (opens new window)

Assume the sub has a length of k. Check every possible k-length substring of s (Let's call it ori) with sub. For character pair ori[i], sub[i] at each index i, if they are not equal and the mapping doesn't exist in mappings, then we can't change this substring to sub.

If none of the k-length substrings works, return False.

DETAILS

def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
        def helper(s, p):
            for ch1, ch2 in zip(s, p):
                if ch1 != ch2 and (ch1, ch2) not in sset:
                    return False
            return True
        m, n, sset = len(s), len(sub), set([(p, q) for p, q in mappings])
        for i in range(1 + m - n):
            if helper(sub, s[i:i+n]):
                return True
        return False

D. Count Subarrays With Score Less Than K (opens new window)

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

滑动窗口法，注意到如果固定一个子数组的某一侧，数组的score是随着数组长度严格递增的。所以我们可以关注对于每一个下标j，有多少以j为结尾的子数组是valid的？

如果我们找到数组A[i:j]是valid的最长子数组，因为score随长度严格递减，那么A[i+1:j]显然也是valid的，也就是A[i:j]的所有后缀数组都是可以的，总数量就等于原来子数组A[i:j]的长度

用滑动窗口，维护i,j作为当前子数组的左右下标。

如果当前子数组score大于等于k，我们需要从左侧去掉数字，直到子数组score小于k。

DETAILS

def countSubarrays(self, nums: List[int], k: int) -> int:
        ssum, res, i, j, n = 0, 0, 0, 0, len(nums)
        while j < n:
            ssum += nums[j]
            while i <= j and ssum * (j - i + 1) >= k:
                ssum -= nums[i]
                i += 1           
            if i > j:
                j = i
                continue
            res += 1 + j - i
            j  += 1
        return res