Distinct Echo Substrings Solution in Python

Problem Description

The “Distinct Echo Substrings” problem is about finding identical sequences of characters that repeat consecutively in a given string. For example, in the string “abab”, the substring “ab” is an echo because it appears twice in a row. However, single characters like “a” and “b” do not count as echoes since they do not repeat consecutively.

Code Solution

Here’s the Python solution to the problem:


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        seen = set()

        for k in range(1, len(text) // 2 + 1):  # the target length
            same = 0
            l = 0
            for r in range(k, len(text)):
                if text[l] == text[r]:
                    same += 1
                else:
                    same = 0
                if same == k:
                    seen.add(text[l - k + 1:l + 1])
                    same -= 1
                l += 1

        return len(seen)

Approach

The approach taken in this solution involves iterating through possible lengths of substrings (from 1 to half the length of the string) and using a sliding window technique to check for echoes. For each substring length k, we maintain a count of how many characters match between the two parts of the string. If we find a match that equals k, we add that substring to our set of seen substrings, ensuring that we only keep distinct echoes.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n²)
Space Complexity	O(n)

Real-World Example

Imagine you’re at a party, and you overhear someone repeating a catchy phrase. You think, “Wow, that’s a great line!” and you start to notice how many times it gets repeated throughout the night. Each time you hear it, you mentally note it down. By the end of the night, you’ve got a list of distinct phrases that echoed through the party. This is exactly what the “Distinct Echo Substrings” problem is about—finding those catchy phrases (substrings) that echo back to you!