1316. Distinct Echo Substrings Solution

The problem

Return the number of distinct non-empty substrings of text that can be written as the concatenation of some string with itself (i.e. it can be written as a + a where a is some string).

Example 1:

Input: text = "abcabcabc"
Output: 3
Explanation: The 3 substrings are "abcabc", "bcabca" and "cabcab".

Example 2:

Input: text = "leetcodeleetcode"
Output: 2
Explanation: The 2 substrings are "ee" and "leetcodeleetcode".

Constraints:

1 <= text.length <= 2000
text has only lowercase English letters.

Approach overview

Problem Overview: You are given a string and must count how many distinct echo substrings it contains. A substring is an echo substring if it can be written as a + a, meaning the first half is identical to the second half. The task is not just detecting them but counting unique substrings that satisfy this condition.

Approach 1: Sliding Window with Rolling Hash (O(n^2) time, O(n^2) space)

This approach uses a rolling hash to compare substring halves efficiently. Iterate over possible half lengths L. For each starting index i, compute the hash of s[i : i+L] and s[i+L : i+2L]. If the hashes match, the substring s[i : i+2L] is an echo substring. Store its hash in a set to guarantee uniqueness.

The key insight is that hashing reduces substring comparison from O(L) to O(1). Without hashing, each comparison would require character-by-character checks. A prefix-hash array allows constant-time substring hash extraction. Sliding the window across the string for each length produces an overall O(n^2) time complexity. This technique is common in string problems that require fast substring equality checks.

Approach 2: Dynamic Programming with Longest Common Prefix (O(n^2) time, O(n^2) space)

Dynamic programming can precompute the longest common prefix between every pair of indices. Define dp[i][j] as the length of the common prefix starting at positions i and j. Fill the table from the end of the string toward the start. If s[i] == s[j], then dp[i][j] = 1 + dp[i+1][j+1]; otherwise it is zero.

Once the table is built, check pairs of indices where j > i. If dp[i][j] >= j - i, the substring s[i : j] equals s[j : j + (j - i)], forming an echo substring of length 2 * (j - i). Insert the substring into a set to ensure distinct counting. This approach relies on substring matching through precomputed overlaps instead of hashing.

The DP table effectively answers "how many characters match starting from these two positions" in constant time. That makes it easy to verify echo conditions quickly. The tradeoff is memory usage since the n × n matrix can be large.

Recommended for interviews: The rolling hash solution is usually preferred. It demonstrates strong knowledge of substring hashing, prefix hashes, and set-based deduplication. Interviewers often expect candidates to recognize that naive substring comparisons would be too slow and switch to hashing. The DP method shows good understanding of substring relationships but uses more memory. Both approaches rely heavily on concepts from string processing and hashing.

Approach 1: Sliding Window with Hashing

This approach involves utilizing a sliding window to iterate over possible substrings and employing hashing to detect if a substring is a repeated concatenation of a smaller substring. The advantage of hashing is that it allows comparison of substrings in O(1) time, making the solution efficient.

Python

def distinct_echo_substrs(text):
    n = len(text)
    seen = set()
    for length in range(1, n // 2 + 1):
        hash_set = set()
        for i in range(n - 2 * length + 1):
            if text[i:i + length] == text[i + length:i + 2 * length]:
                hash_set.add(text[i:i + 2 * length])
        seen.update(hash_set)
    return len(seen)

Java

import java.util.HashSet;

public class EchoSubstr {
    public static int distinctEchoSubstrs(String text) {
        int n = text.length();
        HashSet<String> seen = new HashSet<>();
        for (int length = 1; length <= n / 2; length++) {
            HashSet<String> hashSet = new HashSet<>();
            for (int i = 0; i <= n - 2 * length; i++) {
                if (text.substring(i, i + length).equals(text.substring(i + length, i + 2 * length))) {
                    hashSet.add(text.substring(i, i + 2 * length));
                }
            }
            seen.addAll(hashSet);
        }
        return seen.size();
    }
}

C++

#include <unordered_set>
#include <string>

int distinctEchoSubstrs(std::string text) {
    int n = text.length();
    std::unordered_set<std::string> seen;
    for (int length = 1; length <= n / 2; ++length) {
        std::unordered_set<std::string> hashSet;
        for (int i = 0; i <= n - 2 * length; ++i) {
            if (text.substr(i, length) == text.substr(i + length, length)) {
                hashSet.insert(text.substr(i, 2 * length));
            }
        }
        seen.insert(hashSet.begin(), hashSet.end());
    }
    return seen.size();
}

JavaScript

function distinctEchoSubstrs(text) {
    const n = text.length;
    const seen = new Set();
    for (let length = 1; length <= Math.floor(n / 2); length++) {
        const hashSet = new Set();
        for (let i = 0; i + 2 * length <= n; i++) {
            if (text.substring(i, i + length) === text.substring(i + length, i + 2 * length)) {
                hashSet.add(text.substring(i, i + 2 * length));
            }
        }
        hashSet.forEach(s => seen.add(s));
    }
    return seen.size;
}

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

int distinctEchoSubstrs(const char* text) {
    int length = strlen(text);
    char** seen = (char**)malloc(length * length * sizeof(char*));
    int seenSize = 0;
    int uniqueCount = 0;

    for (int len = 1; len <= length / 2; len++) {
        for (int i = 0; i <= length - 2 * len; i++) {
            if (strncmp(&text[i], &text[i + len], len) == 0) {
                char* substr = (char*)malloc((2 * len + 1) * sizeof(char));
                strncpy(substr, &text[i], 2 * len);
                substr[2 * len] = '\0';
                // Check if substring is already seen
                int isUnique = 1;
                for (int j = 0; j < seenSize; j++) {
                    if (strcmp(seen[j], substr) == 0) {
                        isUnique = 0;
                        break;
                    }
                }
                if (isUnique) {
                    seen[seenSize++] = substr;
                    uniqueCount++;
                } else {
                    free(substr);
                }
            }
        }
    }
    for (int i = 0; i < seenSize; i++) {
        free(seen[i]);
    }
    free(seen);
    return uniqueCount;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int DistinctEchoSubstrs(string text) {
        int n = text.Length;
        HashSet<string> seen = new HashSet<string>();
        for (int length = 1; length <= n / 2; length++) {
            HashSet<string> hashSet = new HashSet<string>();
            for (int i = 0; i <= n - 2 * length; i++) {
                if (text.Substring(i, length).Equals(text.Substring(i + length, length))) {
                    hashSet.Add(text.Substring(i, 2 * length));
                }
            }
            seen.UnionWith(hashSet);
        }
        return seen.Count;
    }
}

This Python function calculates the number of distinct echo substrings by iterating over possible substring lengths up to half of the text length. It uses a sliding window to compare each substring of length 'length' with the succeeding substring of the same length. If they are equal, it stores the combined substring in a set to ensure uniqueness.

Complexity

Time Complexity: O(n^2), where n is the length of the text. Space Complexity: O(n), for storing hash values.

Try this approach in the editor

Approach 2: Dynamic Programming

This approach uses Dynamic Programming (DP) to keep track of repeated substring patterns. A DP table can help store results of previous computations, thus optimizing the check for repeated substrings by re-using calculated solutions.

Python

def distinct_echo_substrs(text):
    n = len(text)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    seen = set()
    for i in range(n - 1, -1, -1):
        for j in range(i + 1, n):
            if text[i] == text[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1
                if i + dp[i][j] <= j:
                    seen.add(text[i:j+1])
    return len(seen)

Java

import java.util.HashSet;

public class EchoSubstrDP {
    public static int distinctEchoSubstrs(String text) {
        int n = text.length();
        int[][] dp = new int[n][n];
        HashSet<String> seen = new HashSet<>();
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (text.charAt(i) == text.charAt(j)) {
                    dp[i][j] = dp[i + 1][j + 1] + 1;
                    if (dp[i][j] >= j - i) {
                        seen.add(text.substring(i, j + 1));
                    }
                }
            }
        }
        return seen.size();
    }
}

C++

#include <unordered_set>
#include <vector>
#include <string>

int distinctEchoSubstrs(std::string text) {
    int n = text.size();
    std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
    std::unordered_set<std::string> seen;
    for (int i = n - 2; i >= 0; --i) {
        for (int j = i + 1; j < n; ++j) {
            if (text[i] == text[j]) {
                dp[i][j] = dp[i + 1][j + 1] + 1;
                if (dp[i][j] >= j - i) {
                    seen.insert(text.substr(i, j - i + 1));
                }
            }
        }
    }
    return seen.size();
}

JavaScript

function distinctEchoSubstrs(text) {
    const n = text.length;
    const dp = Array.from({length: n}, () => Array(n).fill(0));
    const seen = new Set();
    for (let i = n - 2; i >= 0; i--) {
        for (let j = i + 1; j < n; j++) {
            if (text[i] === text[j]) {
                dp[i][j] = dp[i + 1][j + 1] + 1;
                if (dp[i][j] >= j - i) {
                    seen.add(text.substring(i, j + 1));
                }
            }
        }
    }
    return seen.size;
}

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

int distinctEchoSubstrs(const char* text) {
    int length = strlen(text);
    int** dp = (int**)malloc(length * sizeof(int*));
    for(int i = 0; i < length; ++i) {
        dp[i] = (int*)calloc(length, sizeof(int));
    }
    char** seen = (char**)malloc(length * length * sizeof(char*));
    int seenSize = 0;
    int uniqueCount = 0;

    for (int i = length - 2; i >= 0; i--) {
        for (int j = i + 1; j < length; j++) {
            if (text[i] == text[j]) {
                dp[i][j] = dp[i + 1][j + 1] + 1;
                if (dp[i][j] >= j - i) {
                    int exists = 0;
                    char* substr = (char*)malloc((j - i + 2) * sizeof(char));
                    strncpy(substr, &text[i], j - i + 1);
                    substr[j - i + 1] = '\0';
                    for (int k = 0; k < seenSize; k++) {
                        if (strcmp(seen[k], substr) == 0) {
                            exists = 1;
                            break;
                        }
                    }
                    if (!exists) {
                        seen[seenSize++] = substr;
                        uniqueCount++;
                    } else {
                        free(substr);
                    }
                }
            }
        }
    }
    for(int i = 0; i < length; ++i) {
        free(dp[i]);
    }
    free(dp);
    for (int i = 0; i < seenSize; i++) {
        free(seen[i]);
    }
    free(seen);
    return uniqueCount;

using System;
using System.Collections.Generic;

public class Solution {
    public int DistinctEchoSubstrs(string text) {
        int n = text.Length;
        int[,] dp = new int[n, n];
        HashSet<string> seen = new HashSet<string>();
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (text[i] == text[j]) {
                    dp[i, j] = dp[i + 1, j + 1] + 1;
                    if (dp[i, j] >= j - i) {
                        seen.Add(text.Substring(i, j - i + 1));
                    }
                }
            }
        }
        return seen.Count;
    }
}

The Python implementation uses a 2D DP table where dp[i][j] stores the length of the longest common suffix of text[i:] and text[j:]. It stores unique echo substrings in a set. The function performs checks to ensure that only valid echo substrings are stored.

Complexity

Time Complexity: O(n^2). Space Complexity: O(n^2) due to the DP table.

Try this approach in the editor

Approach 3: Default Approach

func distinctEchoSubstrings(text string) int {
	n := len(text)
	base := 131
	h := make([]int, n+10)
	p := make([]int, n+10)
	p[0] = 1
	for i, c := range text {
		t := int(c-'a') + 1
		p[i+1] = p[i] * base
		h[i+1] = h[i]*base + t
	}
	get := func(l, r int) int {
		return h[r] - h[l-1]*p[r-l+1]
	}
	vis := map[int]bool{}
	for i := 0; i < n-1; i++ {
		for j := i + 1; j < n; j += 2 {
			k := (i + j) >> 1
			a, b := get(i+1, k+1), get(k+2, j+1)
			if a == b {
				vis[a] = true
			}
		}
	}
	return len(vis)
}

Rust

use std::collections::HashSet;

const BASE: u64 = 131;

impl Solution {
    #[allow(dead_code)]
    pub fn distinct_echo_substrings(text: String) -> i32 {
        let n = text.len();
        let mut vis: HashSet<u64> = HashSet::new();
        let mut base_vec: Vec<u64> = vec![1; n + 1];
        let mut hash_vec: Vec<u64> = vec![0; n + 1];

        // Initialize the base vector & hash vector
        for i in 0..n {
            let cur_char = ((text.chars().nth(i).unwrap() as u8) - ('a' as u8) + 1) as u64;
            // Update base vector
            base_vec[i + 1] = base_vec[i] * BASE;
            // Update hash vector
            hash_vec[i + 1] = hash_vec[i] * BASE + cur_char;
        }

        // Traverse the text to find the result pair, using rolling hash
        for i in 0..n - 1 {
            for j in i + 1..n {
                // Prevent overflow
                let k = i + (j - i) / 2;
                let left = Self::get_hash(i + 1, k + 1, &base_vec, &hash_vec);
                let right = Self::get_hash(k + 2, j + 1, &base_vec, &hash_vec);
                if left == right {
                    vis.insert(left);
                }
            }
        }

        vis.len() as i32
    }

    #[allow(dead_code)]
    fn get_hash(start: usize, end: usize, base_vec: &Vec<u64>, hash_vec: &Vec<u64>) -> u64 {
        hash_vec[end] - hash_vec[start - 1] * base_vec[end - start + 1]
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sliding Window with Hashing	Time Complexity: O(n^2), where n is the length of the text. Space Complexity: O(n), for storing hash values.
Dynamic Programming	Time Complexity: O(n^2). Space Complexity: O(n^2) due to the DP table.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Sliding Window with Rolling Hash	O(n^2)	O(n^2)	Best general solution for large strings; avoids expensive substring comparisons
Dynamic Programming (LCP Table)	O(n^2)	O(n^2)	Useful when precomputing substring matches or practicing DP-based string analysis

Frequently asked questions

Is Distinct Echo Substrings easy or hard?

Distinct Echo Substrings is classified as a Hard problem on LeetCode. It requires knowledge of rolling hash or advanced dynamic programming for substring comparison, along with careful handling of duplicates using hashing or sets.

Distinct Echo Substrings Python/Java solution

Python and Java implementations typically use rolling hash with prefix arrays and a set to store unique substring hashes. The algorithm iterates over possible half-lengths and starting indices, compares hash values of the two halves, and counts distinct matches.

How to solve Distinct Echo Substrings in O(n)?

No widely accepted O(n) algorithm exists for this problem. Most competitive programming and interview solutions rely on rolling hash or longest common prefix dynamic programming, both running in O(n^2) time. These methods efficiently compare substring halves while avoiding repeated character comparisons.

What is the best approach for Distinct Echo Substrings?

The rolling hash approach is typically the best solution. It compares the two halves of candidate substrings using prefix hashes, allowing O(1) equality checks. Iterating over all half-lengths and start positions results in O(n^2) time with a hash set used to store distinct echo substrings.

Is Distinct Echo Substrings asked at Google/Amazon/Meta?

Problems involving substring hashing and repeated patterns appear frequently in interviews at companies like Google and Meta. Distinct Echo Substrings specifically tests rolling hash, substring comparison, and deduplication techniques commonly expected in advanced string problems.

What data structure is used in Distinct Echo Substrings?

Common solutions use hash sets to track unique substrings and prefix hash arrays for rolling hash calculations. Some implementations also use a dynamic programming table to compute longest common prefixes between index pairs.

What is the time complexity of Distinct Echo Substrings?

The optimal known solutions run in O(n^2) time. Both rolling hash and dynamic programming approaches check substring pairs while ensuring fast equality checks. Space complexity is usually O(n^2) due to storing substrings or maintaining a DP table.

Distinct Echo Substrings solution and explanation

The problem

Approach overview

Approach 1: Sliding Window with Hashing

Approach 2: Dynamic Programming

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Distinct Echo Substrings solution and explanation

The problem

Approach overview

Approach 1: Sliding Window with Hashing

Approach 2: Dynamic Programming

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems