tag

#suffix-array

22 pages tagged

Practice › LeetCode › LeetCode 19xx ›

LeetCode 1977 - Number of Ways to Separate Numbers

LeetCode Problem 1977 Difficulty: 🔴 Hard Topics: String, Dynamic Programming, Suffix Array Solution Problem Understanding The problem asks us to determine the number of ways a string of digits, num , can be split into a sequence of positive integers that are non-decreasing and have no leading zeros . Essentially, each valid partition represents a sequence of numbers that could have been originally written down before the commas were removed....
leetcode Hard string dynamic-programming suffix-array May 29, 2026
Practice › LeetCode › LeetCode 32xx ›

LeetCode 3213 - Construct String with Minimum Cost

LeetCode Problem 3213 Difficulty: 🔴 Hard Topics: Array, String, Dynamic Programming, Suffix Array Solution Problem Understanding The problem asks us to construct a target string target by repeatedly appending strings from a given array words , where each word has an associated cost in costs . The goal is to determine the minimum total cost to construct target exactly. If it is impossible to form target from the given words,...
leetcode Hard array string dynamic-programming suffix-array May 29, 2026
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...
leetcode Hard string binary-search rolling-hash suffix-array string-matching hash-function May 29, 2026
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...
leetcode Hard array binary-search rolling-hash suffix-array hash-function May 29, 2026
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,...
leetcode Medium string binary-search dynamic-programming rolling-hash suffix-array hash-function May 28, 2026
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,...
leetcode Medium string trie rolling-hash suffix-array hash-function May 28, 2026
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...
leetcode Hard string binary-search sliding-window rolling-hash suffix-array hash-function May 28, 2026
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)...
leetcode string binary-search dynamic-programming rolling-hash suffix-array May 14, 2026
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:...
leetcode string binary-search sliding-window rolling-hash suffix-array May 14, 2026
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

DC7 Suffix Array

DC7 Suffix Array Sort DC7 is a generalization of DC3 suffix array construction. It splits suffix positions into residue classes modulo 7 and recursively sorts a subset of suffixes, then induces the remaining order. The goal is to reduce comparison depth by encoding suffixes into fixed length tuples and merging sorted partitions. Problem Given a string $T$ of length $n$, construct its suffix array: $$ SA[0 \dots n-1] $$ such...
algorithms sorting suffix-array dc7 string
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Suffix Array Binary Search

Suffix Array Binary Search Suffix array binary search finds a pattern in a text by searching over the sorted list of suffixes. A suffix array stores the starting positions of all suffixes of a text in lexicographic order. Since the suffixes are sorted, binary search can locate the range of suffixes that begin with a given pattern. Problem Given a text $T$, its suffix array SA , and a pattern...
algorithms searching suffix-array string
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Skew Suffix Array Sort

Skew Suffix Array Sort Skew suffix array sort, also known as the DC3 algorithm, constructs a suffix array in linear time by recursively sorting a subset of suffixes whose positions are not divisible by 3. The remaining suffixes are then merged using the already computed order. Problem Given a string $S$ of length $n$, construct its suffix array: $$ SA = \text{sorted indices of all suffixes of } S $$...
algorithms sorting string-processing suffix-array dc3
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

DC3 Suffix Array

Skew Suffix Array Sort (DC3) DC3, also called skew algorithm, builds a suffix array in linear time by splitting suffix positions into residue classes modulo 3 and recursively sorting a subset. It reduces the full suffix ordering problem into a smaller problem, then merges results using rank comparisons. Problem Given a string $T$ of length $n$, construct its suffix array: $$ SA[0 \dots n-1] $$ such that all suffixes are...
algorithms sorting suffix-array dc3 string
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

DC3 Suffix Array Sort

DC3 Suffix Array Sort DC3 suffix array sort is the concrete formulation of the skew algorithm based on a difference cover modulo 3. It builds the suffix array in linear time by sorting a subset of suffixes, assigning them ranks, and merging with the remaining suffixes. It is widely used in high-performance string processing systems. Problem Given a string $S$ of length $n$, construct the suffix array: $$ SA =...
algorithms sorting string-processing suffix-array dc3
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Suffix Array Doubling Sort

Suffix Array Doubling Sort Suffix array doubling sort constructs a suffix array by iteratively sorting prefixes of length $1, 2, 4, 8, \dots$ until all suffixes are uniquely ranked. It replaces full suffix comparisons with rank comparisons that double in length each round. Problem Given a string $T$ of length $n$, construct a suffix array: $$ SA[0 \dots n-1] $$ such that suffixes of $T$ are sorted lexicographically. Idea Each...
algorithms sorting suffix-array string
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Suffix Array Radix Sort

Suffix Array Radix Sort Suffix array radix sort is the radix-optimized version of the suffix array doubling method. It still sorts suffixes by rank pairs, but uses counting sort or radix sort instead of comparison sorting. This reduces each doubling round from comparison sorting over pairs to linear sorting over integer ranks. Problem Given a string $S$ of length $n$, construct the suffix array: $$ SA = \text{sorted indices of...
algorithms sorting string-processing suffix-array radix-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Induced Sorting

Induced Sorting Induced sorting is a technique used to construct suffix arrays in linear time. Instead of sorting all suffixes directly, it sorts a subset of suffixes and then induces the order of the remaining ones. This idea forms the foundation of modern linear-time suffix array algorithms such as SA-IS. Problem Given a string $S$ of length $n$, construct the suffix array: $$ SA = \text{sorted indices of all suffixes...
algorithms sorting string-processing suffix-array induced-sorting
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Suffix Array Doubling Sort

Suffix Array Doubling Sort Suffix array doubling sort builds a suffix array by repeatedly sorting suffixes based on prefixes of length (2^k). Each step uses previously computed ranks to compare longer prefixes efficiently. This method avoids direct string comparison and reduces the problem to sorting integer pairs. Problem Given a string (S) of length (n), construct the suffix array: $$ SA = \text{sorted indices of all suffixes of } S...
algorithms sorting string-processing suffix-array
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

SA-IS Suffix Array

SA-IS Suffix Array Construction SA-IS constructs a suffix array in linear time by classifying characters and recursively sorting a reduced problem of LMS substrings. It is one of the most efficient practical algorithms for suffix array construction. Problem Given a string $T$ of length $n$, construct its suffix array: $$ SA[0 \dots n-1] $$ such that suffixes of $T$ are in lexicographic order. Key Idea Each position in the string...
algorithms sorting suffix-array sa-is string
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

SA IS

SA IS SA IS is a linear-time suffix array construction algorithm. It sorts a carefully chosen subset of suffixes, called LMS suffixes, then induces the order of all remaining suffixes from them. It is one of the standard practical algorithms for building suffix arrays in linear time. Problem Given a string $S$ of length $n$, construct its suffix array: $$ SA = \text{sorted indices of all suffixes of } S...
algorithms sorting string-processing suffix-array sa-is
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

LCP Accelerated Suffix Search

LCP Accelerated Suffix Search LCP accelerated suffix search improves suffix array binary search by using the Longest Common Prefix information to avoid repeated character comparisons. Instead of comparing the pattern against suffixes from scratch at every step, the algorithm reuses previously computed prefix matches. Problem Given a text $T$, suffix array SA , LCP array LCP , and a pattern $P$, determine whether $P$ occurs in $T$. Return true if...
algorithms searching suffix-array lcp-array string
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

DC7 Suffix Array Sort

DC7 Suffix Array Sort DC7 suffix array sort is a linear-time suffix array construction method based on a difference cover modulo 7. It generalizes the DC3 idea by sorting a larger sampled subset of suffixes, then using the resulting ranks to sort and merge the remaining suffixes. The method is mostly of theoretical and specialist interest. DC3 and SA-IS are more common in practice. Problem Given a string $S$ of...
algorithms sorting string-processing suffix-array dc7