Approach 1: Naive
The first naive approach would be generating all the substrings of the string and counting the different numbers of substrings. The idea is to use HashSet data structure to count the number of distinct substrings in a string.
Implementation
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class Solution {
public static int distinct(String s)
{
// HashSet for distinct substrings
Set<String> ans = new HashSet<String>();
for (int i = 0; i <= s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
// To add the substrings in the set.
// It will eliminate the duplicates
ans.add(s.substring(i, j));
}
}
// This will return the count i.e
// the size of the hashset
return ans.size();
}
// Driver Code
public static void main(String[] args)
{
String s = "abc";
System.out.println(distinct(s));
}
}
Output
6
Complexity Analysis
Time Complexity: The overall complexity of this approach becomes O(n^3log(n2)).
Space Complexity: O(n)
Also see, Euclid GCD Algorithm
Approach 2:
The idea is to create a Trie of all suffixes of a given string. Once the Trie is constricted, our answer is the total number of nodes in the constructed Trie. The idea is to insert the character not already present in the Trie. For example, the below diagram represents Trie of all suffixes for "ababa." The total number of nodes is 10, which is our answer.
Sourcetutorialspoint
Each root represents a prefix of words existing in the Trie to node path of a Trie. We are suffixes in this case. As a result, each node corresponds to a prefix of suffixes.
A prefix of a suffix of "str" is every substring of the string "str."
Implementation
import java.io.*;
class Solution {
static class TrieNode{
TrieNode child[];
boolean end;
TrieNode(){
this.child = new TrieNode[26];
this.end = false;
}
}
static TrieNode root = new TrieNode();
static void insert(String s){
TrieNode curr = root;
for(char ch : s.toCharArray()){
int i = ch  'a';
if(curr.child[i] == null)
curr.child[i] = new TrieNode();
curr = curr.child[i];
}
curr.end = true;
}
public static int substring(String s){
// To count the total number of strings
int count = 0;
for (int i = 0; i <= s.length(); i++){
TrieNode temp = root;
for (int j = i; j < s.length(); j++){
char ch = s.charAt(j);
// Add it in trie, if character is not present
if(temp.child[ch  'a'] == null){
temp.child[ch  'a'] = new TrieNode();
temp.end = true;
count++;
}
// Move to the next character
temp = temp.child[ch  'a'];
}
}
return count;
}
// Main function
public static void main (String[] args) {
int count = substring("abc");
System.out.println(count);
}
}
Output
6
Complexity Analysis
Time Complexity: The time complexity is O(n^2)
Space Complexity: O(n)*26. T is the reduced space complexity.
Check out this problem  Find Duplicate In Array
Frequently Asked Questions

What do you mean by HashSet data structure?
HashSet is a data structure in which duplicate values are not allowed. It is mainly used for its less time complexity consuming in insert and delete operations.

What do you mean by a substring?
It is a contiguous sequence of characters in a string. For example, "is the" is a substring of "This is the programming language."

How many approaches can be there to compute the different substrings in a string?
There can be many approaches to finding the distinct substrings in a string. But we have implemented two approaches in the Java language.
Key Takeaways
This blog has covered the following approaches:
 The first approach is the naive approach to compute the different substrings in a string, where we were using a HashSet data structure to store the substrings.

The second approach is the efficient one where we are using a unique data structure called Suffix Arrays/ Trie, and you can learn about it in great detail here.
Also, you can try more problems based on similar concepts or questions contributed by creative programmers like Ninja and substrings, Find all distinct palindromic substrings of a given string, and many more.
Recommended problems 
Coding Ninjas Studio is a onestop destination for various DSA questions typically asked in interviews to practice more such problems.
Keep Learning, Keep Growing!!!