Distinct Echo Substrings - Solution & Explanation
Problem Statement
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 <= 2000texthas 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.
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.
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.
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.
Approach 3: Default Approach
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 | — |
Detailed 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 |
Video Solution
Distinct Echo Substrings • Pepcoding • 4,088 views views
Watch 6 more video solutions →Frequently Asked Questions
Is Distinct Echo Substrings easy or hard?
Distinct Echo Substrings Python/Java solution
How to solve Distinct Echo Substrings in O(n)?
What is the best approach for Distinct Echo Substrings?
Is Distinct Echo Substrings asked at Google/Amazon/Meta?
What data structure is used in Distinct Echo Substrings?
What is the time complexity of Distinct Echo Substrings?
Ready to solve this problem?
Practice Distinct Echo Substrings with our built-in code editor and test cases.
Practice on FleetCode