Distinct Echo Substrings - Practice Coding Problems

Distinct Echo Substrings - Problem

Given a string text, return the number of distinct non-empty substrings that can be written as the concatenation of some string with itself.

In other words, count all substrings that can be written as a + a where a is some non-empty string.

For example, if text = "abcabc", then "abcabc" can be written as "abc" + "abc", so it counts as an echo substring.

Input & Output

Example 1 — Basic Case

$ Input: text = "abab"

› Output: 2

💡 Note: Echo substrings are "abab" ("ab" + "ab") and "baba" doesn't exist, but "ab" appears at positions 0-1, and full "abab" is "ab"+"ab". Also "ba" at position 1-2 forms "baba" but that's not in the string. Actually, we have "ab" and "abab" as valid echoes.

Example 2 — Longer String

$ Input: text = "aabaaba"

› Output: 4

💡 Note: Echo substrings: "aa" (positions 0-1), "aaba" ("aa"+"ba"), "abaa" ("ab"+"aa"), and "baab" ("ba"+"ab")

Example 3 — No Echoes

$ Input: text = "a"

› Output: 0

💡 Note: Single character cannot form an echo substring (need at least length 2)

Constraints

1 ≤ text.length ≤ 2000
text consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String text with potential echo patterns

Process

Find all substrings of form a+a where a is non-empty

Output

Count of distinct echo substrings

Key Takeaway

🎯 Key Insight: An echo substring has even length with identical first and second halves

Asked in

G Google 15 F Facebook 12

The key insight is that an echo substring must have even length where the first half exactly matches the second half. The brute force approach checks all substrings in O(n³), while rolling hash optimizes comparisons to O(n²). Best approach uses rolling hash for efficient substring comparison. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Rolling Hash Optimization	O(n²)	O(n²)	Use rolling hash to efficiently compare substring halves without string operations
Brute Force	O(n³)	O(n³)	Check all substrings of even length to see if first half equals second half

Rolling Hash Optimization — Algorithm Steps

Precompute rolling hash for the entire string
For each starting position and length, compute hash of first half
Compute hash of second half using rolling hash
Compare hashes instead of strings, use set for deduplication

Visualization

Tap to expand

Step-by-Step Walkthrough

Precompute Hashes

Calculate rolling hash for entire string

Compare Halves

Use hash to compare first and second halves

Deduplicate

Store unique echo substrings

Code -

solution.c — C

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

#define MAX_LEN 2000
#define MAX_SUBSTRINGS 10000
#define MOD 1000000007
#define BASE 31

int solution(char* text) {
    int n = strlen(text);
    
    // Precompute powers of BASE
    long long powBase[MAX_LEN + 1];
    powBase[0] = 1;
    for (int i = 1; i <= n; i++) {
        powBase[i] = (powBase[i-1] * BASE) % MOD;
    }
    
    // Precompute prefix hashes
    long long hashPrefix[MAX_LEN + 1];
    hashPrefix[0] = 0;
    for (int i = 0; i < n; i++) {
        hashPrefix[i+1] = (hashPrefix[i] * BASE + text[i]) % MOD;
    }
    
    char substrings[MAX_SUBSTRINGS][MAX_LEN];
    int count = 0;
    
    // Check all even-length substrings
    for (int i = 0; i < n; i++) {
        for (int length = 2; length <= n - i; length += 2) {
            int mid = length / 2;
            long long hash1 = (hashPrefix[i + mid] - hashPrefix[i] * powBase[mid] % MOD + MOD) % MOD;
            long long hash2 = (hashPrefix[i + length] - hashPrefix[i + mid] * powBase[mid] % MOD + MOD) % MOD;
            
            if (hash1 == hash2) {
                // Check if already exists
                char substring[MAX_LEN];
                strncpy(substring, text + i, length);
                substring[length] = '\0';
                
                int exists = 0;
                for (int k = 0; k < count; k++) {
                    if (strcmp(substrings[k], substring) == 0) {
                        exists = 1;
                        break;
                    }
                }
                
                if (!exists && count < MAX_SUBSTRINGS) {
                    strcpy(substrings[count], substring);
                    count++;
                }
            }
        }
    }
    
    return count;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n²)

O(n²) substrings × O(1) hash comparison for each substring

⚠ Quadratic Growth

Space Complexity

O(n²)

Set stores up to O(n²) hash values or substrings

⚠ Quadratic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

847 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