Distinct Echo Substrings — Solution in Python, Java & C++
Distinct Echo Substrings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Distinct Echo Substrings is a hard coding problem on strings, hash table and trie, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Strings, Hash Table, Trie, Rolling Hash
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An echo is a non-empty string that is some string written twice in a row, a + a (for example abab or zz).
Return the number of distinct non-empty substrings of text that are echoes. Equal substrings found at different positions count once.
Example 1
Input: text = "kaikai"
Output: 1
Explanation: Only `kaikai` itself (`kai` + `kai`).
Example 2
Input: text = "aaaa"
Output: 2
Explanation: `aa` and `aaaa`.
Example 3
Input: text = "abababab"
Output: 3
Explanation: `abab`, `baba` and `abababab`.
Constraints
1 <= text.length <= 2000text has only lowercase English letters
Hints for Distinct Echo Substrings
Hint 1
An echo of length
2Lstarting atineedstext[i..i+L) == text[i+L..i+2L), i.e. the suffixes atiandi + Lshare at leastLcharacters.Hint 2
Precompute
lcp[i][j], the longest common prefix of the suffixes starting atiandj, withlcp[i][j] = lcp[i+1][j+1] + 1when the characters match. Every echo test is thenO(1).Hint 3
To count each distinct echo once, only count an occurrence if the same substring did not occur earlier:
text[i..i+2L)appeared at somej < iexactly whenlcp[j][i] >= 2L. Precompute the maximum oflcp[j][i]overj < i.
How to solve Distinct Echo Substrings
With an all-pairs suffix LCP table, both questions — "is this an echo?" and "has this exact substring appeared earlier?" — become O(1) comparisons, so every (start, half-length) pair is tested once and each distinct echo is counted at its first occurrence.
Approach
- Build
lcp[i][j]for0 <= i < j < nfrom the bottom-right:lcp[i][j] = text[i] == text[j] ? lcp[i+1][j+1] + 1 : 0. - For each start
i, letprev[i]be the maximum oflcp[j][i]overj < i— the longest prefix of the suffix atithat also starts somewhere earlier. - For each
iand each half-lengthLwithi + 2L <= n: the substringtext[i..i+2L)is an echo iflcp[i][i+L] >= L, and it is a first occurrence ifprev[i] < 2L. Count it when both hold. - Return the count.
Why it works
lcp[i][i+L] >= L is exactly the statement that the two halves are equal. A substring of length 2L starting at i occurs earlier iff some j < i has lcp[j][i] >= 2L, iff prev[i] >= 2L. So each distinct echo is counted precisely at its leftmost occurrence and nowhere else.
Complexity
- Time —
O(n^2) - Space —
O(n^2) for the table
Pitfalls
- Putting the substrings themselves in a set costs
O(n)per insertion —O(n^3)in the worst case. - A rolling hash works but risks collisions unless double-hashed; the LCP table is exact.
aaaacontainsaathree times but it is one distinct echo.
Reference solution
Python
def distinctEchoSubstrings(text: str) -> int:
n = len(text)
lcp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
row, below = lcp[i], lcp[i + 1]
ci = text[i]
for j in range(n - 1, i, -1):
if text[j] == ci:
row[j] = below[j + 1] + 1
count = 0
for i in range(n):
prev = 0
for j in range(i):
if lcp[j][i] > prev:
prev = lcp[j][i]
row = lcp[i]
for half in range(1, (n - i) // 2 + 1):
if row[i + half] >= half and prev < 2 * half:
count += 1
return countJava
public static int distinctEchoSubstrings(String text) {
int n = text.length();
int[][] lcp = new int[n + 1][n + 1];
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j > i; j--) {
if (text.charAt(i) == text.charAt(j)) lcp[i][j] = lcp[i + 1][j + 1] + 1;
}
}
int count = 0;
for (int i = 0; i < n; i++) {
int prev = 0;
for (int j = 0; j < i; j++) prev = Math.max(prev, lcp[j][i]);
for (int half = 1; i + 2 * half <= n; half++) {
if (lcp[i][i + half] >= half && prev < 2 * half) count++;
}
}
return count;
}C++
int distinctEchoSubstrings(string text) {
int n = text.size();
vector<vector<int>> lcp(n + 1, vector<int>(n + 1, 0));
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j > i; j--) {
if (text[i] == text[j]) lcp[i][j] = lcp[i + 1][j + 1] + 1;
}
}
int count = 0;
for (int i = 0; i < n; i++) {
int prev = 0;
for (int j = 0; j < i; j++) prev = max(prev, lcp[j][i]);
for (int half = 1; i + 2 * half <= n; half++) {
if (lcp[i][i + half] >= half && prev < 2 * half) count++;
}
}
return count;
}JavaScript
var distinctEchoSubstrings = function(text) {
var n = text.length;
var lcp = [];
for (var r = 0; r <= n; r++) lcp.push(new Int32Array(n + 1));
for (var i = n - 1; i >= 0; i--) {
for (var j = n - 1; j > i; j--) {
if (text.charCodeAt(i) === text.charCodeAt(j)) lcp[i][j] = lcp[i + 1][j + 1] + 1;
}
}
var count = 0;
for (var i2 = 0; i2 < n; i2++) {
var prev = 0;
for (var j2 = 0; j2 < i2; j2++) if (lcp[j2][i2] > prev) prev = lcp[j2][i2];
for (var half = 1; i2 + 2 * half <= n; half++) {
if (lcp[i2][i2 + half] >= half && prev < 2 * half) count++;
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets