Number of Distinct Substrings in a String

Number of Distinct Substrings in a String - Problem

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.

For example, if s = "abc", the substrings are: "a", "b", "c", "ab", "bc", "abc", and the empty string "". However, since we only count distinct substrings, duplicates are counted only once.

Input & Output

Example 1 — Simple String

$ Input: s = "abc"

› Output: 6

💡 Note: The distinct substrings are: "a", "b", "c", "ab", "bc", "abc". Total count is 6.

Example 2 — Repeated Characters

$ Input: s = "aaa"

› Output: 3

💡 Note: The distinct substrings are: "a", "aa", "aaa". Even though there are multiple 'a' characters, we only count unique substrings.

Example 3 — Single Character

$ Input: s = "a"

› Output: 1

💡 Note: Only one substring possible: "a". Count is 1.

Constraints

1 ≤ s.length ≤ 1000
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String s = "abc"

Process

Generate all substrings and count unique ones

Output

Return count = 6

Key Takeaway

🎯 Key Insight: Use a hash set to automatically eliminate duplicate substrings while counting

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to generate all possible substrings and use a hash set to automatically handle uniqueness. The brute force approach with set storage works well for the given constraints. Best approach is brute force with set for simplicity. Time: O(n³), Space: O(n³)

Common Approaches

Approach	Time	Space	Notes
✓ Rolling Hash Optimization	O(n²)	O(n²)	Use rolling hash to efficiently compute substring hashes without creating actual substrings
Brute Force with Set	O(n³)	O(n³)	Generate all possible substrings and store them in a set to ensure uniqueness

Rolling Hash Optimization — Algorithm Steps

Choose hash parameters (base and modulo)
For each starting position, compute rolling hash
Add hash to set for uniqueness
Return set size

Visualization

Tap to expand

Step-by-Step Walkthrough

Hash

Compute polynomial hash for each substring

Store

Add hash values to set

Count

Return unique hash count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEN 1000
#define MAX_HASHES 500000

int solution(char* s) {
    static long long hashes[MAX_HASHES];
    int count = 0;
    int n = strlen(s);
    long long base = 31;
    long long mod = 1000000007LL;
    
    for (int i = 0; i < n; i++) {
        long long hashVal = 0;
        long long power = 1;
        for (int j = i; j < n; j++) {
            hashVal = (hashVal + (s[j] - 'a' + 1) * power) % mod;
            power = (power * base) % mod;
            
            // Check if hash already exists
            int exists = 0;
            for (int k = 0; k < count; k++) {
                if (hashes[k] == hashVal) {
                    exists = 1;
                    break;
                }
            }
            
            if (!exists) {
                hashes[count] = hashVal;
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char s[MAX_LEN];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops to generate positions, constant time hash computation

⚠ Quadratic Growth

Space Complexity

O(n²)

Set stores up to O(n²) hash values, each taking O(1) space

⚠ Quadratic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Rolling Hash Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler