Distinct Echo Substrings - Video Solutions

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.