hashtable.md

• 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+)