hashtable

• Hash Table

  • 1573.Number-of-Ways-to-Split-a-String (M)

  • Hash+Prefix

    • Reviewed

    • Todo

Hash Table

049.Group-Anagrams (M+) 149.Max-Points-on-a-Line (H) 166.Fraction-to-Recurring-Decimal (M) 170.Two-Sum-III-Data-structure-design (M) 392.Is-Subsequence (H-) 204.Count Primes (M) 274.H-Index (H) 325.Maximum-Size-Subarray-Sum-Equals-k (M) 409.Longest-Palindrome (M) 447.Number-of-Boomerangs (E+) 438.Find-All-Anagrams-in-a-String (M+) 356.Line-Reflection (H-) 594.Longest-Harmonious-Subsequence (M+) 532.K-diff-Pairs-in-an-Array (E+) 424.Longest-Repeating-Character-Replacement （H） 446.Arithmetic-Slices-II-Subsequence (H) 128.Longest-Consecutive-Sequence (H-) 753.Cracking-the-Safe (H) 890.Find-and-Replace-Pattern (M+) 939.Minimum-Area-Rectangle (M+) 982.Triples-with-Bitwise-AND-Equal-To-Zero (M+) (TBD) 1074.Number-of-Submatrices-That-Sum-to-Target (M+) 1224.Maximum-Equal-Frequency (H-) 1487.Making-File-Names-Unique (M+)

1573.Number-of-Ways-to-Split-a-String (M)

• Think out solution in 10 minutes. https://expl.ai/MYVQNNA

• Have the following error message:

  1. Does not mod number in edge case

  2. Whether expected result is integer or float

class Solution:
    def numWays(self, s: str) -> int:
        histogram = defaultdict(lambda: 0)
        counter = 0
        for i in range(len(s)):
            counter += 1 if s[i] == "1" else 0
            histogram[counter] += 1

        modNum = 10 ** 9 + 7            
        if counter == 0:
            return (len(s) - 1) * (len(s) - 2) // 2 % modNum

        if counter % 3 != 0:
            return 0
        else:
            divided = counter // 3
            return histogram[divided * 2] * histogram[divided] % modNum

Hash+Prefix

# using LC 525 as an example
class Solution:
    def findMaxLength(self, nums: List[int]) -> int:

        prefixSumToIndex = dict()
        prefixSumToIndex[0] = -1

        longest = 0
        prefixSum = 0
        for i in range(len(nums)):
            prefixSum += -1 if nums[i] == 0 else 1
            if prefixSum in prefixSumToIndex:
                longest = max(longest, i - prefixSumToIndex[prefixSum])
            else:
                prefixSumToIndex[prefixSum] = i

        return longest

Reviewed

525.Contiguous-Array (M)

Todo

930.Binary-Subarrays-With-Sum (M) 1442.Count-Triplets-That-Can-Form-Two-Arrays-of-Equal-XOR (H-) 1524.Number-of-Sub-arrays-With-Odd-Sum (M) 974.Subarray-Sums-Divisible-by-K (M) 1590.Make-Sum-Divisible-by-P (M+) 1658.Minimum-Operations-to-Reduce-X-to-Zero (M) 1371.Find-the-Longest-Substring-Containing-Vowels-in-Even-Counts (H-) 1542.Find-Longest-Awesome-Substring (H-) 1915.Number-of-Wonderful-Substrings (M+) 1983.Widest-Pair-of-Indices-With-Equal-Range-Sum (M+)