# Distinct Echo Substrings
**Difficulty:** HARD
[External](https://leetcode.com/problems/distinct-echo-substrings)
Canonical: https://scaleengineer.com/dsa/problems/distinct-echo-substrings
**Patterns:** [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Data structures:** String, Trie
---
## 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.

# Approaches
## Brute-force Iteration
This is a straightforward brute-force approach that systematically checks every possible substring that could be an echo substring. It iterates through all possible starting positions and lengths, and for each candidate, it performs a direct string comparison to verify if it's an echo substring. A `HashSet` is used to count only the distinct ones.
**Time:** O(n^3). There are two nested loops, giving O(n^2) combinations of starting positions `i` and half-lengths `len`. Inside the inner loop, creating and comparing substrings of length `len` takes O(len) time. The total complexity is roughly the sum of `len` over all iterations, which amounts to O(n^3). · **Space:** O(n^2). The `HashSet` can store up to O(n^2) distinct substrings. The total length of all distinct substrings stored in the set is also bounded by O(n^2).
**Pros:** The logic is simple and easy to understand and implement.
**Cons:** The time complexity of O(n^3) is too slow for the given constraints (n <= 2000) and will likely result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
The core idea is to generate and test all potential echo substrings. An echo substring must have an even length, say `2 * len`. It is formed by concatenating a string `a` of length `len` with itself. We can iterate through all possible starting positions `i` and all possible half-lengths `len`. For each pair of `(i, len)`, we check if the substring of length `len` starting at `i` is equal to the substring of length `len` starting at `i + len`. If they are equal, we have found a valid echo substring, which we add to a `HashSet` to ensure that our final count is of distinct substrings.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int distinctEchoSubstrings(String text) {
        int n = text.length();
        Set<String> found = new HashSet<>();
        
        // i is the starting index of the potential echo substring
        for (int i = 0; i < n; i++) {
            // len is the length of the first half 'a'
            // The full substring has length 2 * len
            for (int len = 1; i + 2 * len <= n; len++) {
                String s1 = text.substring(i, i + len);
                String s2 = text.substring(i + len, i + 2 * len);
                
                if (s1.equals(s2)) {
                    // Found an echo substring. Add the full string 'a+a' to the set.
                    // Note: Adding just 's1' would also work and be slightly more memory efficient,
                    // as a1+a1 == a2+a2 if and only if a1 == a2.
                    found.add(text.substring(i, i + 2 * len));
                }
            }
        }
        
        return found.size();
    }
}
```
### Algorithm
- Initialize an empty `HashSet<String>` to store the unique echo substrings found.
- Iterate through every possible starting position `i` from `0` to `n-1`, where `n` is the length of the text.
- For each starting position `i`, iterate through every possible length `len` for the first half of a potential echo substring. The loop for `len` runs as long as the full substring of length `2 * len` is within the bounds of the text (i.e., `i + 2 * len <= n`).
- Inside the loops, extract the two adjacent substrings of length `len`: `first_half = text.substring(i, i + len)` and `second_half = text.substring(i + len, i + 2 * len)`.
- Compare `first_half` and `second_half`. If they are identical, it means we've found an echo substring.
- Add the full echo substring `text.substring(i, i + 2 * len)` to the `HashSet`. The set automatically handles duplicates.
- After all iterations, the size of the `HashSet` is the number of distinct echo substrings.

## Rolling Hash Optimization
This approach optimizes the brute-force method by replacing the expensive O(L) string comparison with an O(1) hash comparison. It uses the Rabin-Karp algorithm with a rolling hash technique. To make the solution robust against hash collisions, double hashing (using two different hash functions) is employed. This reduces the time complexity significantly, making it efficient enough for the given constraints.
**Time:** O(n^2). The precomputation step takes O(n) time. The nested loops run in O(n^2). Inside the loops, all operations (calculating substring hashes, comparing them, and inserting into the set) take O(1) time. The total time complexity is dominated by the nested loops. · **Space:** O(n^2). We use O(n) space for the precomputed hash and power arrays. The `HashSet` can store up to O(n^2) unique hash pairs in the worst case.
**Pros:** Efficient O(n^2) time complexity, which passes the given constraints.; Highly reliable with double hashing, making collisions extremely unlikely.
**Cons:** The implementation is more complex than the brute-force approach.; Requires careful handling of modular arithmetic to prevent overflow and negative results.
### Explanation
The bottleneck in the brute-force approach is the repeated substring comparison. We can optimize this by using polynomial rolling hash. The hash of a substring can be calculated in O(1) time after an initial O(n) precomputation of prefix hashes and powers of a base.

To be confident that a hash match implies a string match, we use two different hash functions. The probability of two different strings having the same hash value for two different well-chosen hash functions is extremely low. This allows us to avoid the actual character-by-character string comparison.

The algorithm proceeds with the same nested loops as the brute-force approach, but inside the loop, it compares hash values instead of strings. The unique echo substrings are counted by storing their hash values in a `HashSet`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int distinctEchoSubstrings(String text) {
        int n = text.length();
        // Use two different pairs of prime base and modulus for double hashing
        long p1 = 31, m1 = 1_000_000_007;
        long p2 = 37, m2 = 1_000_000_009;

        long[] p1_pow = new long[n + 1];
        long[] h1 = new long[n + 1];
        long[] p2_pow = new long[n + 1];
        long[] h2 = new long[n + 1];

        p1_pow[0] = 1;
        p2_pow[0] = 1;

        // Precompute powers and prefix hashes
        for (int i = 0; i < n; i++) {
            p1_pow[i + 1] = (p1_pow[i] * p1) % m1;
            h1[i + 1] = (h1[i] * p1 + text.charAt(i) - 'a' + 1) % m1;
            p2_pow[i + 1] = (p2_pow[i] * p2) % m2;
            h2[i + 1] = (h2[i] * p2 + text.charAt(i) - 'a' + 1) % m2;
        }

        Set<Long> found = new HashSet<>();
        for (int i = 0; i < n; i++) {
            for (int len = 1; i + 2 * len <= n; len++) {
                long hash1_a = getHash(h1, p1_pow, i, i + len, m1);
                long hash1_b = getHash(h1, p1_pow, i + len, i + 2 * len, m1);

                if (hash1_a == hash1_b) {
                    long hash2_a = getHash(h2, p2_pow, i, i + len, m2);
                    long hash2_b = getHash(h2, p2_pow, i + len, i + 2 * len, m2);
                    if (hash2_a == hash2_b) {
                        // Hashes match for both functions, add to set.
                        // Combine the two hashes into a single long to use as a key.
                        found.add(hash1_a * m2 + hash2_a);
                    }
                }
            }
        }
        return found.size();
    }

    // Helper to get hash of substring text[i..j-1]
    private long getHash(long[] h, long[] p_pow, int i, int j, long m) {
        long raw_hash = h[j] - (h[i] * p_pow[j - i]) % m;
        return (raw_hash + m) % m; // Ensure result is non-negative
    }
}
```
### Algorithm
- Choose two different pairs of (base, modulus) for two independent hash functions to minimize collisions.
- Precompute the powers of both bases up to `n`.
- Precompute the prefix hashes of the input `text` using both hash functions. This allows calculating the hash of any substring in O(1).
- Initialize a `HashSet` to store unique hash representations of the found echo substrings. A pair of `long`s or a single combined `long` can be used as the key.
- Iterate through all starting positions `i` from `0` to `n-1`.
- For each `i`, iterate through all possible half-lengths `len` such that `i + 2 * len <= n`.
- In O(1) time, calculate the two hashes for the first half `text.substring(i, i + len)`.
- In O(1) time, calculate the two hashes for the second half `text.substring(i + len, i + 2 * len)`.
- If the hashes for the first half match the hashes for the second half for both hash functions, we consider it a valid echo substring.
- Add the hash pair (or combined hash) of the first half to the `HashSet`.
- The final answer is the size of the `HashSet`.

# Solutions
### Java

```java
class Solution { private long [] h ; private long [] p ; public int distinctEchoSubstrings ( String text ) { int n = text . length (); int base = 131 ; h = new long [ n + 10 ]; p = new long [ n + 10 ]; p [ 0 ] = 1 ; for ( int i = 0 ; i < n ; ++ i ) { int t = text . charAt ( i ) - 'a' + 1 ; h [ i + 1 ] = h [ i ] * base + t ; p [ i + 1 ] = p [ i ] * base ; } Set < Long > vis = new HashSet <>(); for ( int i = 0 ; i < n - 1 ; ++ i ) { for ( int j = i + 1 ; j < n ; j += 2 ) { int k = ( i + j ) >> 1 ; long a = get ( i + 1 , k + 1 ); long b = get ( k + 2 , j + 1 ); if ( a == b ) { vis . add ( a ); } } } return vis . size (); } private long get ( int i , int j ) { return h [ j ] - h [ i - 1 ] * p [ j - i + 1 ]; } }
```

### CPP

```cpp
typedef unsigned long long ull ; class Solution { public: int distinctEchoSubstrings ( string text ) { int n = text . size (); int base = 131 ; vector < ull > p ( n + 10 ); vector < ull > h ( n + 10 ); p [ 0 ] = 1 ; for ( int i = 0 ; i < n ; ++ i ) { int t = text [ i ] - 'a' + 1 ; p [ i + 1 ] = p [ i ] * base ; h [ i + 1 ] = h [ i ] * base + t ; } unordered_set < ull > vis ; for ( int i = 0 ; i < n - 1 ; ++ i ) { for ( int j = i + 1 ; j < n ; j += 2 ) { int k = ( i + j ) >> 1 ; ull a = get ( i + 1 , k + 1 , p , h ); ull b = get ( k + 2 , j + 1 , p , h ); if ( a == b ) vis . insert ( a ); } } return vis . size (); } ull get ( int l , int r , vector < ull >& p , vector < ull >& h ) { return h [ r ] - h [ l - 1 ] * p [ r - l + 1 ]; } };
```

### Python

```python
class Solution : def distinctEchoSubstrings ( self , text : str ) -> int : def get ( l , r ): return ( h [ r ] - h [ l - 1 ] * p [ r - l + 1 ]) % mod n = len ( text ) base = 131 mod = int ( 1e9 ) + 7 h = [ 0 ] * ( n + 10 ) p = [ 1 ] * ( n + 10 ) for i , c in enumerate ( text ): t = ord ( c ) - ord ( 'a' ) + 1 h [ i + 1 ] = ( h [ i ] * base ) % mod + t p [ i + 1 ] = ( p [ i ] * base ) % mod vis = set () for i in range ( n - 1 ): for j in range ( i + 1 , n , 2 ): k = ( i + j ) >> 1 a = get ( i + 1 , k + 1 ) b = get ( k + 2 , j + 1 ) if a == b : vis . add ( a ) return len ( vis )
```