Distinct Echo Substrings

Hard
1267.

Distinct Echo Substrings

Distinct Echo Substrings is a hard coding problem on strings, hash table and trie, asked in Amazon and Google interviews.

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 <= 2000
  • text has only lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} text
 * @return {number}
 */
var distinctEchoSubstrings = function(text) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 2000
  • text has only lowercase English letters

Hints for Distinct Echo Substrings

  1. Hint 1

    An echo of length 2L starting at i needs text[i..i+L) == text[i+L..i+2L), i.e. the suffixes at i and i + L share at least L characters.

  2. Hint 2

    Precompute lcp[i][j], the longest common prefix of the suffixes starting at i and j, with lcp[i][j] = lcp[i+1][j+1] + 1 when the characters match. Every echo test is then O(1).

  3. 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 some j < i exactly when lcp[j][i] >= 2L. Precompute the maximum of lcp[j][i] over j < 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

  1. Build lcp[i][j] for 0 <= i < j < n from the bottom-right: lcp[i][j] = text[i] == text[j] ? lcp[i+1][j+1] + 1 : 0.
  2. For each start i, let prev[i] be the maximum of lcp[j][i] over j < i — the longest prefix of the suffix at i that also starts somewhere earlier.
  3. For each i and each half-length L with i + 2L <= n: the substring text[i..i+2L) is an echo if lcp[i][i+L] >= L, and it is a first occurrence if prev[i] < 2L. Count it when both hold.
  4. 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.
  • aaaa contains aa three 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 count

Java

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