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 <= 2000text has only lowercase English letters.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.
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.
Time Complexity: O(n^2), where n is the length of the text. Space Complexity: O(n), for storing hash values.
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.
Time Complexity: O(n^2). Space Complexity: O(n^2) due to the DP table.
| 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 | — |
| 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 |
Distinct Echo Substrings • Pepcoding • 4,001 views views
Watch 6 more video solutions →Practice Distinct Echo Substrings with our built-in code editor and test cases.
Practice on FleetCode