Trie Variation for a Hard Leetcode Problem

Here is the problem: Number of Distinct Substrings in a String - LeetCode

1698. Number of Distinct Substrings in a String

Hard

Given a string s, return the number of distinct substrings of s.

A substring of a string is obtained by deleting any number of characters (possibly zero) from the front of the string and any number (possibly zero) from the back of the string.

 

Example 1:

Input: s = "aabbaba"
Output: 21
Explanation: The set of distinct strings is ["a","b","aa","bb","ab","ba","aab","abb","bba","aba","aabb","abba","bbab","baba","aabba","abbab","bbaba","aabbab","abbaba","aabbaba"]

Example 2:

Input: s = "abcdefg"
Output: 28

 

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.

Accepted

118

Submissions

242

My first several attempts resulted in TLE. Approach was simple: N^2 nested loops, get the substring, compare with a hashtable. But the "get the substring" is actually expensive, and even the hash was expensive resulting in a runtime >> N^2.

When I went thru the discussions list, I noticed everyone mentioning "Tries". The variation I came up with worked quite well: every time that you try to add a character, return the Trie node for that character. That way, this operation will always be constant time. Always. And you end up with a truly N^2-time complexity. Since N=500, this results in 250K iterations, which is very fast. Code is down below, and Merry Christmas! ACC.

public class Solution
{
    public int CountDistinct(string s)
    {
        if (String.IsNullOrEmpty(s)) return 0;

        int retVal = 0;
        Trie trie = new Trie();
        Trie anchor = trie;
        for (int i = 0; i < s.Length; i++)
        {
            trie = anchor;
            for (int j = i; j < s.Length; j++)
            {
                bool isWord = false;
                trie = trie.Add(s[j], ref isWord);
                if (!isWord) retVal++;
            }
        }

        return retVal;
    }
}
public class Trie
{
    private Hashtable nodes = null;

    public Trie()
    {
        nodes = new Hashtable();
    }

    public Trie Add(char c, ref bool isWord)
    {
        if (!nodes.ContainsKey(c))
        {
            isWord = false;
            Trie trie = new Trie();
            nodes.Add(c, trie);
            return trie;
        }
        else
        {
            isWord = true;
            return (Trie)nodes[c];
        }
    }
}