How hard is LeetCode 1316. Distinct Echo Substrings?

LeetCode 1316. Distinct Echo Substrings is rated Hard on LeetCode.

What is the time complexity of LeetCode 1316. Distinct Echo Substrings?

The Python solution on this page runs in O(total characters).

What is the space complexity of LeetCode 1316. Distinct Echo Substrings?

The Python solution on this page uses O(total characters) auxiliary space.

What topics does LeetCode 1316. Distinct Echo Substrings cover?

LeetCode 1316. Distinct Echo Substrings is tagged Trie, String, Hash Function and Rolling Hash on LeetCode.

Distinct Echo Substrings — LeetCode 1316 Python Solution

HardTrieStringHash FunctionRolling Hash

Problem: #1316
Pattern: Trie
Reading time: 4 min
Source: leetcode.com

The problem

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

Input: text = "abcabcabc"
Output: 3
Explanation: The 3 substrings are "abcabc", "bcabca" and "cabcab".

Python solution

Python

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        def get(l, r):
            return (h[r] - h[l - 1] * p[r - l + 1]) % mod

        n = len(text)
        base = 131
        mod = int(1e9) + 7
        h = [0] * (n + 10)
        p = [1] * (n + 10)
        for i, c in enumerate(text):
            t = ord(c) - ord('a') + 1
            h[i + 1] = (h[i] * base) % mod + t
            p[i + 1] = (p[i] * base) % mod
        vis = set()
        for i in range(n - 1):
            for j in range(i + 1, n, 2):
                k = (i + j) >> 1
                a = get(i + 1, k + 1)
                b = get(k + 2, j + 1)
                if a == b:
                    vis.add(a)
        return len(vis)

Complexity

Measure	Complexity
Time	O(total characters)
Space	O(total characters) auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 1316. Distinct Echo Substrings is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Trie.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1316. Distinct Echo Substrings?: LeetCode 1316. Distinct Echo Substrings is rated Hard on LeetCode.
What is the time complexity of LeetCode 1316. Distinct Echo Substrings?: The Python solution on this page runs in O(total characters).
What is the space complexity of LeetCode 1316. Distinct Echo Substrings?: The Python solution on this page uses O(total characters) auxiliary space.
What topics does LeetCode 1316. Distinct Echo Substrings cover?: LeetCode 1316. Distinct Echo Substrings is tagged Trie, String, Hash Function and Rolling Hash on LeetCode.