Skip to content

String Hashing

Table of Contents

28. Find the Index of the First Occurrence in a String

28. Find the Index of the First Occurrence in a String - Python Solution
from template import LPS


# Brute Force
def strStrBF(haystack: str, needle: str) -> int:
    m, n = len(haystack), len(needle)
    for i in range(m - n + 1):
        if haystack[i : i + n] == needle:
            return i
    return -1


# KMP
def strStrKMP(haystack: str, needle: str) -> int:
    lps = LPS(needle)
    m, n = len(haystack), len(needle)
    j = 0

    for i in range(m):
        while j > 0 and haystack[i] != needle[j]:
            j = lps[j - 1]
        if haystack[i] == needle[j]:
            j += 1
        if j == n:
            return i - n + 1
    return -1


# |------------|------------------|---------|
# |  Approach  |       Time       |  Space  |
# |------------|------------------|---------|
# | Brute Force| O((m - n) * n)   | O(1)    |
# | KMP        | O(m + n)         | O(n)    |
# |------------|------------------|---------|


haystack = "hello"
needle = "ll"
print(strStrBF(haystack, needle))  # 2
print(strStrKMP(haystack, needle))  # 2

187. Repeated DNA Sequences

  • LeetCode | LeetCode CH (Medium)

  • Tags: hash table, string, bit manipulation, sliding window, rolling hash, hash function

1316. Distinct Echo Substrings

1297. Maximum Number of Occurrences of a Substring

2261. K Divisible Elements Subarrays

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, hash table, trie, rolling hash, hash function, enumeration

3213. Construct String with Minimum Cost

1367. Linked List in Binary Tree

1044. Longest Duplicate Substring

  • LeetCode | LeetCode CH (Hard)

  • Tags: string, binary search, sliding window, rolling hash, suffix array, hash function

718. Maximum Length of Repeated Subarray

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, binary search, dynamic programming, sliding window, rolling hash, hash function

718. Maximum Length of Repeated Subarray - Python Solution
from typing import List


def findLength(nums1: List[int], nums2: List[int]) -> int:
    m = len(nums1)
    n = len(nums2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    length = 0

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if nums1[i - 1] == nums2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            if length < dp[i][j]:
                length = dp[i][j]

    return length


print(findLength([1, 2, 3, 2, 1], [3, 2, 1, 4, 7]))  # 3

1923. Longest Common Subpath

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, binary search, rolling hash, suffix array, hash function

3292. Minimum Number of Valid Strings to Form Target II

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, string, binary search, dynamic programming, segment tree, rolling hash, string matching, hash function

2168. Unique Substrings With Equal Digit Frequency

  • LeetCode | LeetCode CH (Medium)

  • Tags: hash table, string, rolling hash, counting, hash function

1554. Strings Differ by One Character

1062. Longest Repeating Substring

  • LeetCode | LeetCode CH (Medium)

  • Tags: string, binary search, dynamic programming, rolling hash, suffix array, hash function

Comments