Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1316.html

1316. Distinct Echo Substrings (Hard)

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 <= 2000
  • text has only lowercase English letters.

Related Topics:
String, Rolling Hash

Solution 1. Rolling Hash

// OJ: https://leetcode.com/problems/distinct-echo-substrings/
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
    int distinctEchoSubstrings(string s) {
        int N = s.size(), mod = 1e8 + 7, cnt = 0;
        vector<long> v(N);
        for (int len = 1; len <= N / 2; ++len) {
            long hash = s[0] - 'a', p = 1;
            unordered_set<string> seen;
            for (int i = 1; i < N; ++i) {
                if (i < len) {
                    hash = (hash * 26 + s[i] - 'a') % mod;
                    p = (p * 26) % mod;
                } else {
                    hash = ((hash - (s[i - len] - 'a') * p) * 26 + s[i] - 'a') % mod;
                    if (hash < 0) hash += mod;
                    if (i - 2 * len + 1 >= 0 && v[i - len] == hash) {
                        auto a = s.substr(i - 2 * len + 1, len);
                        if (seen.count(a)) continue;
                        seen.insert(a);
                        if (a == s.substr(i - len + 1, len)) ++cnt;
                    }
                }
                v[i] = hash;
            }
        }
        return cnt;
    }
};
  • class Solution {
        public int distinctEchoSubstrings(String text) {
            Set<String> substringsSet = new HashSet<String>();
            int length = text.length();
            for (int i = 0; i < length; i++) {
                int maxLength = length - i;
                for (int j = 2; j <= maxLength; j += 2) {
                    String substr1 = text.substring(i, i + j / 2), substr2 = text.substring(i + j / 2, i + j);
                    if (substr1.equals(substr2))
                        substringsSet.add(substr1 + substr2);
                }
            }
            return substringsSet.size();
        }
    }
    
  • // OJ: https://leetcode.com/problems/distinct-echo-substrings/
    // Time: O(N^2)
    // Space: O(N)
    class Solution {
    public:
        int distinctEchoSubstrings(string s) {
            int N = s.size(), mod = 1e8 + 7, cnt = 0;
            vector<long> v(N);
            for (int len = 1; len <= N / 2; ++len) {
                long hash = s[0] - 'a', p = 1;
                unordered_set<string> seen;
                for (int i = 1; i < N; ++i) {
                    if (i < len) {
                        hash = (hash * 26 + s[i] - 'a') % mod;
                        p = (p * 26) % mod;
                    } else {
                        hash = ((hash - (s[i - len] - 'a') * p) * 26 + s[i] - 'a') % mod;
                        if (hash < 0) hash += mod;
                        if (i - 2 * len + 1 >= 0 && v[i - len] == hash) {
                            auto a = s.substr(i - 2 * len + 1, len);
                            if (seen.count(a)) continue;
                            seen.insert(a);
                            if (a == s.substr(i - len + 1, len)) ++cnt;
                        }
                    }
                    v[i] = hash;
                }
            }
            return cnt;
        }
    };
    
  • 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)
    
    
    

All Problems

All Solutions