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;
    }
};

• Java
• C++
• Python
• Go

• 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();
      }
  }
  
  ############
  
  class Solution {
      private long[] h;
      private long[] p;
  
      public int distinctEchoSubstrings(String text) {
          int n = text.length();
          int base = 131;
          h = new long[n + 10];
          p = new long[n + 10];
          p[0] = 1;
          for (int i = 0; i < n; ++i) {
              int t = text.charAt(i) - 'a' + 1;
              h[i + 1] = h[i] * base + t;
              p[i + 1] = p[i] * base;
          }
          Set<Long> vis = new HashSet<>();
          for (int i = 0; i < n - 1; ++i) {
              for (int j = i + 1; j < n; j += 2) {
                  int k = (i + j) >> 1;
                  long a = get(i + 1, k + 1);
                  long b = get(k + 2, j + 1);
                  if (a == b) {
                      vis.add(a);
                  }
              }
          }
          return vis.size();
      }
  
      private long get(int i, int j) {
          return h[j] - h[i - 1] * p[j - i + 1];
      }
  }
  

• // 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)
  
  
  

• func distinctEchoSubstrings(text string) int {
  	n := len(text)
  	base := 131
  	h := make([]int, n+10)
  	p := make([]int, n+10)
  	p[0] = 1
  	for i, c := range text {
  		t := int(c-'a') + 1
  		p[i+1] = p[i] * base
  		h[i+1] = h[i]*base + t
  	}
  	get := func(l, r int) int {
  		return h[r] - h[l-1]*p[r-l+1]
  	}
  	vis := map[int]bool{}
  	for i := 0; i < n-1; i++ {
  		for j := i + 1; j < n; j += 2 {
  			k := (i + j) >> 1
  			a, b := get(i+1, k+1), get(k+2, j+1)
  			if a == b {
  				vis[a] = true
  			}
  		}
  	}
  	return len(vis)
  }
  

All Problems

All Solutions