suffix-array

Practice › LeetCode › LeetCode 39xx ›

LeetCode 3934 - Smallest Unique Subarray

LeetCode Problem 3934 Difficulty: 🔴 Hard Topics: Array, Hash Table, Binary Search, Rolling Hash, Suffix Array, Hash Function Solution Problem Understanding The problem asks us to find the smallest possible length of a contiguous subarray such that there exists at least one subarray of that length that appears exactly once in the entire array. In other words, for a fixed length L , we look at every subarray of size...

Practice › LeetCode › LeetCode 37xx ›

LeetCode 3735 - Lexicographically Smallest String After Reverse II

LeetCode Problem 3735 Difficulty: 🔴 Hard Topics: String, Binary Search, Rolling Hash, Suffix Array, Hash Function Solution Problem Understanding The problem is asking us to manipulate a string s of length n in order to produce the lexicographically smallest possible string after exactly one operation. The operation allows you to choose an integer k between 1 and n and either reverse the first k characters or reverse the last k...

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 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 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....

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,...

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 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 (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 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:...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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 =...

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...

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 $$...

#suffix-array

LeetCode 3934 - Smallest Unique Subarray

LeetCode 3735 - Lexicographically Smallest String After Reverse II

LeetCode 1923 - Longest Common Subpath

LeetCode 2223 - Sum of Scores of Built Strings

LeetCode 1977 - Number of Ways to Separate Numbers

LeetCode 3213 - Construct String with Minimum Cost

LeetCode 1062 - Longest Repeating Substring

LeetCode 1044 - Longest Duplicate Substring

LeetCode 1698 - Number of Distinct Substrings in a String

LeetCode 1062: Longest Repeating Substring

LeetCode 1044: Longest Duplicate Substring

Suffix Array Binary Search

SA IS

LCP Accelerated Suffix Search

Suffix Array Doubling Sort

DC7 Suffix Array

Suffix Array Radix Sort

SA-IS Suffix Array

DC7 Suffix Array Sort

DC3 Suffix Array

Suffix Array Doubling Sort

DC3 Suffix Array Sort

Induced Sorting

Skew Suffix Array Sort