rolling-hash

Practice › LeetCode › LeetCode 35xx ›

LeetCode 3529 - Count Cells in Overlapping Horizontal and Vertical Substrings

LeetCode Problem 3529 Difficulty: 🟡 Medium Topics: Array, String, Rolling Hash, String Matching, Matrix, Hash Function Solution Problem Understanding We are given a character matrix and a pattern string. The key observation is that the problem defines two unusual traversal orders: A horizontal traversal reads the matrix row by row, from left to right. When a row ends, reading continues at the beginning of the next row. A vertical traversal...

Practice › LeetCode › LeetCode 19xx ›

LeetCode 1960 - Maximum Product of the Length of Two Palindromic Substrings

LeetCode Problem 1960 Difficulty: 🔴 Hard Topics: Two Pointers, String, Rolling Hash, Hash Function Solution LeetCode 1960 - Maximum Product of the Length of Two Palindromic Substrings Problem Understanding The problem asks us to find two non-overlapping odd-length palindromic substrings whose length product is as large as possible. We are given a string s of length up to 10^5 . We must choose two palindromic substrings: The first occupies indices...

Practice › LeetCode › LeetCode 21xx ›

LeetCode 2156 - Find Substring With Given Hash Value

LeetCode Problem 2156 Difficulty: 🔴 Hard Topics: String, Sliding Window, Rolling Hash, Hash Function Solution Problem Understanding This problem asks us to find the earliest substring of length k whose polynomial rolling hash equals a given target value. The hash function is defined as: $$hash(s, p, m) = \left( \sum_{i=0}^{k-1} val(s[i]) \cdot p^i \right) \bmod m$$ where: val('a') = 1 val('b') = 2 ... val('z') = 26 For a substring...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3036 - Number of Subarrays That Match a Pattern II

LeetCode Problem 3036 Difficulty: 🔴 Hard Topics: Array, Rolling Hash, String Matching, Hash Function Solution This guide will be very long, likely exceeding a single message cleanly while still maintaining the level of detail and formatting quality you requested for a reference document. I can provide the complete guide in full , including: Problem Understanding Approaches (Brute Force + Optimal KMP) Algorithm Walkthrough Python Solution Go Solution Worked Examples (step-by-step...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3006 - Find Beautiful Indices in the Given Array I

LeetCode Problem 3006 Difficulty: 🟡 Medium Topics: Two Pointers, String, Binary Search, Rolling Hash, String Matching, Hash Function Solution Problem Understanding The problem gives us a string s and two smaller strings, a and b . We need to find every index i where substring a appears in s , but only if there exists at least one occurrence of substring b close enough to it. More formally, an index...

Practice › LeetCode › LeetCode 24xx ›

LeetCode 2430 - Maximum Deletions on a String

LeetCode Problem 2430 Difficulty: 🔴 Hard Topics: String, Dynamic Programming, Rolling Hash, String Matching, Hash Function Solution Maximum Deletions on a String Problem Understanding The problem gives us a string s consisting only of lowercase English letters. We want to completely delete the string using the maximum possible number of operations. In a single operation, we have two possible actions: Delete the entire remaining string immediately. Delete only the first...

Practice › LeetCode › LeetCode 22xx ›

LeetCode 2261 - K Divisible Elements Subarrays

LeetCode Problem 2261 Difficulty: 🟡 Medium Topics: Array, Hash Table, Trie, Rolling Hash, Hash Function, Enumeration Solution Problem Understanding This problem requires counting the number of distinct subarrays of a given integer array nums that satisfy a specific constraint: each subarray can contain at most k elements divisible by p . A subarray is a contiguous slice of the array, and "distinct" means either differing in length or differing in...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3029 - Minimum Time to Revert Word to Initial State I

LeetCode Problem 3029 Difficulty: 🟡 Medium Topics: String, Rolling Hash, String Matching, Hash Function Solution Problem Understanding The problem gives us a string word and an integer k . Every second, we are forced to perform two operations in sequence: Remove the first k characters from the string. Append any k characters to the end of the string. The appended characters are completely under our control. They do not need...

Practice › LeetCode › LeetCode 32xx ›

LeetCode 3292 - Minimum Number of Valid Strings to Form Target II

LeetCode Problem 3292 Difficulty: 🔴 Hard Topics: Array, String, Binary Search, Dynamic Programming, Greedy, Segment Tree, Rolling Hash, String Matching, Hash Function Solution LeetCode 3292 - Minimum Number of Valid Strings to Form Target II Problem Understanding We are given a collection of strings words and a target string target . A string is considered valid if it is a prefix of at least one word in words . This...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3023 - Find Pattern in Infinite Stream I

LeetCode Problem 3023 Difficulty: 🟡 Medium Topics: Array, Sliding Window, Rolling Hash, String Matching, Interactive, Hash Function Solution Problem Understanding The problem asks us to detect the first occurrence of a given binary pattern within an infinite stream of bits. We are given an object stream that allows us to read one bit at a time using the next() function. Our task is to return the 0-based index in the...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3045 - Count Prefix and Suffix Pairs II

LeetCode Problem 3045 Difficulty: 🔴 Hard Topics: Array, String, Trie, Rolling Hash, String Matching, Hash Function Solution Problem Understanding The problem asks us to count the number of ordered pairs (i, j) in a list of strings words such that i < j and words[i] is both a prefix and a suffix of words[j] . In other words, for a pair to be valid, the smaller-indexed string must appear at...

Practice › LeetCode › LeetCode 19xx ›

LeetCode 1923 - Longest Common Subpath

LeetCode Problem 1923 Difficulty: 🔴 Hard Topics: Array, Binary Search, Rolling Hash, Suffix Array, Hash Function Solution Problem Understanding The problem asks us to find the maximum length of a contiguous sequence of cities that appears in every friend's travel path. Each friend has a path represented as an array of city IDs. A subpath is simply a contiguous segment of that array. We need to determine the longest subpath...

Practice › LeetCode › LeetCode 21xx ›

LeetCode 2168 - Unique Substrings With Equal Digit Frequency

LeetCode Problem 2168 Difficulty: 🟡 Medium Topics: Hash Table, String, Rolling Hash, Counting, Hash Function Solution Problem Understanding The problem gives us a string s consisting only of digits from '0' to '9' . We must count how many distinct substrings satisfy a special condition: Every digit that appears in the substring must appear the same number of times. A substring is a contiguous portion of the string. The substring...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3034 - Number of Subarrays That Match a Pattern I

LeetCode Problem 3034 Difficulty: 🟡 Medium Topics: Array, Rolling Hash, String Matching, Hash Function Solution Problem Understanding The problem asks us to count how many contiguous subarrays of nums match a given relationship pattern . Instead of comparing exact values, the pattern describes how adjacent numbers should relate to each other. Each value in pattern represents a comparison between two consecutive elements in a subarray: 1 means the next number...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3042 - Count Prefix and Suffix Pairs I

LeetCode Problem 3042 Difficulty: 🟢 Easy Topics: Array, String, Trie, Rolling Hash, String Matching, Hash Function Solution LeetCode 3042 - Count Prefix and Suffix Pairs I Problem Understanding The problem gives us an array of strings called words . For every pair of indices (i, j) where i < j , we must determine whether words[i] is both a prefix and a suffix of words[j] . A string is a...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3031 - Minimum Time to Revert Word to Initial State II

LeetCode Problem 3031 Difficulty: 🔴 Hard Topics: String, Rolling Hash, String Matching, Hash Function Solution Problem Understanding The problem requires simulating a repetitive transformation on a string word where, at each second, the first k characters are removed, and then any k characters are appended to the end. The key challenge is to determine the minimum number of seconds required for the string to return exactly to its initial state....

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3008 - Find Beautiful Indices in the Given Array II

LeetCode Problem 3008 Difficulty: 🔴 Hard Topics: Two Pointers, String, Binary Search, Rolling Hash, String Matching, Hash Function Solution LeetCode 3008 - Find Beautiful Indices in the Given Array II Problem Understanding This problem asks us to find every starting index where the substring a appears inside the string s , subject to an additional proximity condition involving another substring b . More specifically, an index i is considered beautiful...

Practice › LeetCode › LeetCode 22xx ›

LeetCode 2223 - Sum of Scores of Built Strings

LeetCode Problem 2223 Difficulty: 🔴 Hard Topics: String, Binary Search, Rolling Hash, Suffix Array, String Matching, Hash Function Solution Problem Understanding The problem gives us a final string s and describes a process where the string is built by repeatedly prepending characters to the front. This means that every intermediate string si is actually a suffix of the final string s . For example, if: s = "abaca" Then: s1...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3037 - Find Pattern in Infinite Stream II

LeetCode Problem 3037 Difficulty: 🔴 Hard Topics: Array, Sliding Window, Rolling Hash, String Matching, Interactive, Hash Function Solution Problem Understanding The problem requires us to detect the first occurrence of a binary pattern within a theoretically infinite stream of bits. The stream is accessed sequentially using the next() method, which returns one bit at a time. Our task is to determine the index in the stream where the given pattern...

Practice › LeetCode › LeetCode 32xx ›

LeetCode 3291 - Minimum Number of Valid Strings to Form Target I

LeetCode Problem 3291 Difficulty: 🟡 Medium Topics: Array, String, Binary Search, Dynamic Programming, Greedy, Trie, Segment Tree, Rolling Hash, String Matching, Hash Function Solution Problem Understanding We are given a list of strings called words and another string called target . The task is to construct target by concatenating several smaller strings, where each smaller string must be a prefix of at least one word in words . A prefix...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 718 - Maximum Length of Repeated Subarray

LeetCode Problem 718 Difficulty: 🟡 Medium Topics: Array, Binary Search, Dynamic Programming, Sliding Window, Rolling Hash, Hash Function Solution Problem Understanding The problem asks us to find the longest contiguous subarray that appears in both input arrays. A subarray is different from a subsequence because the elements must remain adjacent. This distinction is extremely important because many similar problems allow gaps, but this one does not. We are given two...

Practice › LeetCode › LeetCode 11xx ›

LeetCode 1147 - Longest Chunked Palindrome Decomposition

LeetCode Problem 1147 Difficulty: 🔴 Hard Topics: Two Pointers, String, Dynamic Programming, Greedy, Rolling Hash, Hash Function Solution Problem Understanding The problem asks us to decompose a given string text into the largest possible number of contiguous substrings such that the sequence of substrings forms a palindromic pattern. Specifically, the first substring must equal the last substring, the second substring must equal the second-to-last substring, and so on. The goal...

Practice › LeetCode › LeetCode 15xx ›

LeetCode 1554 - Strings Differ by One Character

LeetCode Problem 1554 Difficulty: 🟡 Medium Topics: Hash Table, String, Rolling Hash, Hash Function Solution Problem Understanding This problem gives us an array of unique strings called dict , where every string has the same length. We must determine whether there exists at least one pair of strings that differ by exactly one character at the same position. In other words, we are looking for two strings where: Their lengths...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 214 - Shortest Palindrome

LeetCode Problem 214 Difficulty: 🔴 Hard Topics: String, Rolling Hash, String Matching, Hash Function Solution Problem Understanding The problem gives a string s and asks us to create the shortest possible palindrome by adding characters only at the beginning of the string. A palindrome is a string that reads the same forward and backward. The key restriction is that we are not allowed to insert characters in the middle or...

Practice › LeetCode › LeetCode 13xx ›

LeetCode 1316 - Distinct Echo Substrings

LeetCode Problem 1316 Difficulty: 🔴 Hard Topics: String, Trie, Rolling Hash, Hash Function Solution Problem Understanding The problem asks us to find the number of distinct non-empty substrings of a given string text that can be expressed as the concatenation of some string with itself. In other words, we need to count all substrings of the form a + a , where a is any non-empty string. For example, "abcabc"...

Practice › LeetCode › LeetCode 10xx ›

LeetCode 1044 - Longest Duplicate Substring

LeetCode Problem 1044 Difficulty: 🔴 Hard Topics: String, Binary Search, Sliding Window, Rolling Hash, Suffix Array, Hash Function Solution Here is the complete, detailed technical solution guide for LeetCode 1044 - Longest Duplicate Substring, following your formatting rules exactly. Problem Understanding The problem asks us to find the longest duplicated substring in a given string s . A duplicated substring is a contiguous sequence of characters that appears at least...

Practice › LeetCode › LeetCode 16xx ›

LeetCode 1698 - Number of Distinct Substrings in a String

LeetCode Problem 1698 Difficulty: 🟡 Medium Topics: String, Trie, Rolling Hash, Suffix Array, Hash Function Solution Problem Understanding The problem asks for the total number of distinct substrings of a given string s . A substring is any contiguous sequence of characters from the string, including single-character substrings and the string itself. The output is an integer representing how many unique substrings can be formed from s . For example,...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 187 - Repeated DNA Sequences

LeetCode Problem 187 Difficulty: 🟡 Medium Topics: Hash Table, String, Bit Manipulation, Sliding Window, Rolling Hash, Hash Function Solution Problem Understanding This problem asks us to find all repeated DNA subsequences of a fixed length, specifically length 10 , inside a given DNA string. The input is a string s , where each character represents a DNA nucleotide. The string contains only four possible characters: 'A' 'C' 'G' 'T' We...

Practice › LeetCode › LeetCode 13xx ›

LeetCode 1392 - Longest Happy Prefix

LeetCode Problem 1392 Difficulty: 🔴 Hard Topics: String, Rolling Hash, String Matching, Hash Function Solution Problem Understanding The problem asks us to find the longest substring that is both a prefix and a suffix of the given string s , while also ensuring that the substring is not equal to the entire string itself. A prefix is a substring that starts at index 0 , while a suffix is a...

Practice › LeetCode › LeetCode 10xx ›

LeetCode 1062 - Longest Repeating Substring

LeetCode Problem 1062 Difficulty: 🟡 Medium Topics: String, Binary Search, Dynamic Programming, Rolling Hash, Suffix Array, Hash Function Solution Problem Understanding The problem asks us to find the length of the longest substring that appears at least twice in a given string s . A substring is a contiguous sequence of characters inside a string. The repeated substrings may overlap with each other, which is an important detail. For example,...

Practice › LeetCode › LeetCode 14xx ›

LeetCode 1461 - Check If a String Contains All Binary Codes of Size K

LeetCode Problem 1461 Difficulty: 🟡 Medium Topics: Hash Table, String, Bit Manipulation, Rolling Hash, Hash Function Solution Problem Understanding The problem gives us a binary string s and an integer k . A binary string contains only the characters '0' and '1' . We must determine whether every possible binary code of length k appears somewhere inside s as a substring. A binary code of length k is simply any...

Practice › LeetCode › LeetCode (archived) › LeetCode 10xx ›

LeetCode 1044: Longest Duplicate Substring

Problem Restatement We are given a string s . We need to return the longest substring that appears at least twice. If no such substring exists, return an empty string. The official constraints state that 2 <= s.length <= 3 * 10^4 and s consists only of lowercase English letters. Input and Output Item Meaning Input String s Output Longest duplicate substring (any valid answer accepted) Function shape: def longestDupSubstring(s:...

Practice › LeetCode › LeetCode (archived) › LeetCode 10xx ›

LeetCode 1062: Longest Repeating Substring

Problem Restatement We are given a string s . Return the length of the longest repeating substring (a substring that appears at least twice). If no repeating substring exists, return 0 . The official constraints state that 1 <= s.length <= 2000 and s consists only of lowercase English letters. Input and Output Item Meaning Input String s Output Length of the longest repeating substring Function shape: def longestRepeatingSubstring(s: str)...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 187: Repeated DNA Sequences

Problem Restatement We are given a string s representing a DNA sequence. A DNA sequence contains only these four characters: Character Meaning A Adenine C Cytosine G Guanine T Thymine We need to find all 10-letter-long substrings that appear more than once in s . The answer can be returned in any order. The official statement asks for all 10-letter-long sequences that occur more than once in a DNA molecule....

Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.11 Rolling Hashes

5.11 Rolling Hashes Problem You need to compare many substrings quickly. Direct substring comparison can be expensive because comparing two substrings of length m may take O(m) time. If an algorithm compares many substrings, this cost can dominate the whole computation. A rolling hash assigns each prefix of a string a numeric summary so that the hash of any substring can be computed in constant time after preprocessing. Solution Choose...

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

Rolling Hash Search

Rolling Hash Search Rolling hash search computes a hash over a fixed size window and updates it efficiently as the window moves. It allows substring search in linear time with low constant factors. You use it when scanning large text for patterns or when building string matching algorithms such as Rabin Karp. Problem Given a text $T$ of length $n$ and a pattern $P$ of length $m$, find all indices...

#rolling-hash

LeetCode 3529 - Count Cells in Overlapping Horizontal and Vertical Substrings

LeetCode 1960 - Maximum Product of the Length of Two Palindromic Substrings

LeetCode 2156 - Find Substring With Given Hash Value

LeetCode 3036 - Number of Subarrays That Match a Pattern II

LeetCode 3006 - Find Beautiful Indices in the Given Array I

LeetCode 2430 - Maximum Deletions on a String

LeetCode 2261 - K Divisible Elements Subarrays

LeetCode 3029 - Minimum Time to Revert Word to Initial State I

LeetCode 3292 - Minimum Number of Valid Strings to Form Target II

LeetCode 3023 - Find Pattern in Infinite Stream I

LeetCode 3045 - Count Prefix and Suffix Pairs II

LeetCode 1923 - Longest Common Subpath

LeetCode 2168 - Unique Substrings With Equal Digit Frequency

LeetCode 3034 - Number of Subarrays That Match a Pattern I

LeetCode 3042 - Count Prefix and Suffix Pairs I

LeetCode 3031 - Minimum Time to Revert Word to Initial State II

LeetCode 3008 - Find Beautiful Indices in the Given Array II

LeetCode 2223 - Sum of Scores of Built Strings

LeetCode 3037 - Find Pattern in Infinite Stream II

LeetCode 3291 - Minimum Number of Valid Strings to Form Target I

LeetCode 718 - Maximum Length of Repeated Subarray

LeetCode 1147 - Longest Chunked Palindrome Decomposition

LeetCode 1554 - Strings Differ by One Character

LeetCode 214 - Shortest Palindrome

LeetCode 1316 - Distinct Echo Substrings

LeetCode 1044 - Longest Duplicate Substring

LeetCode 1698 - Number of Distinct Substrings in a String

LeetCode 187 - Repeated DNA Sequences

LeetCode 1392 - Longest Happy Prefix

LeetCode 1062 - Longest Repeating Substring

LeetCode 1461 - Check If a String Contains All Binary Codes of Size K

LeetCode 1044: Longest Duplicate Substring

LeetCode 1062: Longest Repeating Substring

LeetCode 187: Repeated DNA Sequences

5.11 Rolling Hashes

Rolling Hash Search