Distinct Echo Substrings
Problem
Given a string text, return the number of distinct non-empty substrings that can be written in the form a + a, that is, some string a immediately concatenated with an exact copy of itself (an "echo"). Two echo substrings are the same only if they are equal as strings, no matter where they occur.
text = "abcabcabc"3def distinct_echo_substrings(text):
n = len(text)
seen = set()
for half in range(1, n // 2 + 1):
for i in range(0, n - 2 * half + 1):
a = text[i:i + half]
b = text[i + half:i + 2 * half]
if a == b:
seen.add(a)
return len(seen)function distinctEchoSubstrings(text) {
const n = text.length;
const seen = new Set();
for (let half = 1; half <= n / 2; half++) {
for (let i = 0; i + 2 * half <= n; i++) {
const a = text.slice(i, i + half);
const b = text.slice(i + half, i + 2 * half);
if (a === b) seen.add(a);
}
}
return seen.size;
}class Solution {
public int distinctEchoSubstrings(String text) {
int n = text.length();
Set<String> seen = new HashSet<>();
for (int half = 1; half <= n / 2; half++) {
for (int i = 0; i + 2 * half <= n; i++) {
String a = text.substring(i, i + half);
String b = text.substring(i + half, i + 2 * half);
if (a.equals(b)) seen.add(a);
}
}
return seen.size();
}
}int distinctEchoSubstrings(string text) {
int n = text.size();
unordered_set<string> seen;
for (int half = 1; half <= n / 2; half++) {
for (int i = 0; i + 2 * half <= n; i++) {
string a = text.substr(i, half);
string b = text.substr(i + half, half);
if (a == b) seen.insert(a);
}
}
return (int)seen.size();
}Explanation
An echo substring has even length and splits into two equal halves: its first half a and its second half b must be identical, so the whole thing is a + a. To count distinct echoes we only ever need to remember the half a: two echoes are equal exactly when their halves are equal, so a set of halves dedupes them for free.
We try every possible half-length half from 1 up to n / 2 (the full echo is 2 * half long, so it cannot exceed the string). For each half, we slide a window of length 2 * half across the text. At start index i we compare the left block text[i : i+half] with the right block text[i+half : i+2*half]. If they match, the substring is an echo and we add the half to the set.
At the end the answer is simply the number of distinct halves we collected, since each distinct half corresponds to exactly one distinct echo string.
Example: text = "abcabcabc". With half = 3 the window of length 6 finds three matches — "abc" == "abc" at i=0, "bca" == "bca" at i=1, and "cab" == "cab" at i=2 — giving the echoes "abcabc", "bcabca" and "cabcab". No other half-length adds anything new, so the answer is 3.
Comparing whole blocks character by character is clear but costs time per comparison. In the optimized solution you precompute a rolling hash (a polynomial fingerprint) of the string so that the hash of any block is available in O(1); then comparing two halves becomes a single number comparison, and the set stores hashes instead of strings. That keeps the work to O(n²) overall, which is what makes the hard version efficient.