# 1698-Number of Distinct Substrings in a String Using Trie

## Problem Statement

<br>

**Problem Statement:** Given a string of alphabetic characters. Return the count of **distinct** substrings of the string(including the empty string) using the Trie data structure.

**Examples:**

<pre><code><strong>Example 1:
</strong><strong>Input:
</strong> S1= “ababa”
<strong>Output: Total number of distinct substrings : 10
</strong><strong>Explanation: All the substrings of the string are a, ab, aba, abab, ababa, b, ba, bab, baba, a, ab, aba, b, ba, a. Many of the substrings are duplicated. The distinct substrings are a, ab, aba, abab, ababa, b, ba, bab, baba. Total Count of the distinct substrings is 9 + 1(for empty string) = 10.
</strong>


<strong>Example 2:
</strong><strong>Input:
</strong> S1= “ccfdf”

<strong>Output: Total number of distinct substrings : 14
</strong><strong>Explanation:
</strong>All the substrings of the string are c, cc, ccf, ccfd, ccfdf, c, cf, cfd, cfdf, f, fd, fdf, d, df, f. Many of the substrings are duplicated. The distinct substrings are c, cc, ccf, ccfd, ccfdf, cf, cfd, cfdf, f, fd, fdf, d, df. Total Count of the distinct substrings is 13 + 1(for empty string) = 14.
</code></pre>

## Intuition

```
Approach 1:

Brute- Generate all substrings in N^2 and put in set to make unique 
N^2 logn 

optimal- Insert in trie, and it will eliminate the duplicate strings

```

### Links

<https://leetcode.com/problems/number-of-distinct-substrings-in-a-string/description/>

### Video Links

<https://www.youtube.com/watch?v=RV0QeTyHZxo&ab_channel=takeUforward>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Node{
public:
    Node *links[26];
};

class Solution{
public:
    Node *root ;
    Solution(){
        root = new Node();
    }

    int find_subs(string s){
        Node *temp = root;
        int count = 0;
        for(int i=0; i<s.size(); i++){
            for(int j=i; j<s.size(); j++){
                char ch = s[j];
                if(temp->links[ch - 'a'] == nullptr){
                    count++;
                    temp->links[ch - 'a'] = new Node();
                }
                temp = temp->links[ch-'a'];
            }
        }

        return count;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###