Leetcode Problem 1698. Number of Distinct Substrings in a String

1698. Number of Distinct Substrings in a String

Leetcode Solutions

Suffix Array and Longest Common Prefix (LCP)

  1. Construct the suffix array for the string s using the Manber-Myers algorithm.
  2. Compute the LCP array using the Kasai algorithm.
  3. Calculate the total number of possible substrings of s, which is n * (n + 1) / 2, where n is the length of s.
  4. Subtract the sum of the LCP array from the total number of possible substrings to get the number of distinct substrings.
UML Thumbnail

Trie-based Substring Counting

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...