1316. Distinct Echo Substrings
Hard53.0% acceptance21,825 / 41,201 submissions
Asked by 1 company
Topics
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.
Hints
Hint 1
Given a substring of the text, how to check if it can be written as the concatenation of a string with itself ?
Hint 2
We can do that in linear time, a faster way is to use hashing.
Hint 3
Try all substrings and use hashing to check them.