940. Echo Substrings
A sound engineer inspects a coded recording text and looks for echoes: non-empty pieces that are immediately followed by an identical copy of themselves, so the echo itself is some string t written twice in a row, like abab or zz.
Return the number of distinct echo strings that appear as a contiguous substring of text. If the same echo string occurs at several positions, it is counted once.
Aim for time O(n^2) where n is the length of text, and O(n) extra memory per length class. Testing every start and every length character by character takes O(n^3).
Example 1
- Input:
- text = "bonbonbonq"
- Output:
- 3
- Explanation:
The echo substrings are 'bonbon' (it starts at index 0 and again at index 3 but is counted once), 'onbonb', 'nbonbo'; shorter halves such as 'bo' do not repeat immediately, so the answer is 3.
Example 2
- Input:
- text = "ooxooxzz"
- Output:
- 3
- Explanation:
The echoes are 'oo', 'ooxoox' and 'zz', so the answer is 3.
Example 3
- Input:
- text = "kayakers"
- Output:
- 0
- Explanation:
No piece is immediately followed by an identical copy, so the answer is 0.
Constraints
1 ≤ text.length ≤ 1800
text contains only lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n^2)
- Space
- O(n)