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.In #1316 Distinct Echo Substrings, the goal is to count the number of unique substrings that can be written as the concatenation of a string with itself (i.e., xx). A brute-force approach that checks every substring pair would be too slow for large inputs, so efficient string matching techniques are required.
A common strategy uses a rolling hash (Rabin–Karp) to compare substring halves quickly. For every possible length L, you compare the hash of s[i:i+L] with s[i+L:i+2L]. If the hashes match, you have an echo substring candidate. To ensure uniqueness, store the discovered substrings or their hashes in a set.
Another perspective uses a Trie or suffix-based structure to track repeating patterns while scanning the string. However, rolling hash with a hash set is typically simpler and efficient in practice. With careful hashing and substring checks, the algorithm avoids repeated comparisons while identifying distinct echo patterns.
The optimized solution generally runs in around O(n²) time with O(n²) space for storing unique substrings or hashes.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Rolling Hash + Hash Set | O(n^2) | O(n^2) |
| Trie / String Matching Approach | O(n^2) | O(n^2) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Given a substring of the text, how to check if it can be written as the concatenation of a string with itself ?
We can do that in linear time, a faster way is to use hashing.
Try all substrings and use hashing to check them.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems involving substring matching, rolling hash, and string pattern detection are common in FAANG-style interviews. Distinct Echo Substrings tests knowledge of efficient string processing techniques and avoiding brute-force comparisons.
Rolling hash allows constant-time substring hash comparison after preprocessing. Instead of comparing characters one by one, you can compare hash values of two halves of a substring to check if they are identical. This significantly speeds up detecting echo patterns.
A hash set is commonly used to store unique echo substrings or their hashes. Rolling hash helps compare substring halves quickly, while the set guarantees that duplicates are not counted. In some theoretical approaches, tries or suffix structures may also be used.
The most practical approach uses a rolling hash (Rabin–Karp) technique to compare two halves of substrings efficiently. By hashing substrings and storing valid echo substrings in a set, we can avoid repeated comparisons and ensure uniqueness. This reduces the complexity to about O(n^2).