Distinct Echo Substrings

Problem Description

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).

Key Insights

• A substring can be represented as a concatenation of a string with itself if its length is even.
• For a substring of length 2k, it can be divided into two equal parts, each of length k.
• We need to ensure that both halves of the substring are identical to count it as a distinct echo substring.
• Using a rolling hash can efficiently check for distinct substrings while avoiding duplicate counts.

Space and Time Complexity

Time Complexity: O(n^2) - due to the nested loops for substring generation and hashing. Space Complexity: O(n) - for storing the hashes of distinct substrings.

Solution

To solve the problem, we can use a rolling hash approach combined with a set to keep track of distinct echo substrings. The algorithm involves:

1. Iterating through all possible starting indices for substrings.
2. For each starting index, generating substrings of even lengths.
3. For each even-length substring, checking if the first half matches the second half.
4. Using a set to store these distinct echo substrings to ensure uniqueness.

Code Solutions