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).
If a substring can be written as a + a, then its first half and second half are identical. We can use rolling hash to efficiently compare all possible substrings of even length and check if their halves are equal, while collecting only distinct ones.
classSolution {
public:int distinctEchoSubstrings(string text) {
unordered_set<string> st;
int n = text.size();
for (int len =2; len <= n; len +=2) {
for (int i =0; i + len <= n; ++i) {
int mid = i + len /2;
if (text.substr(i, len /2) == text.substr(mid, len /2)) {
st.insert(text.substr(i, len));
}
}
}
return st.size();
}
};
classSolution {
publicintdistinctEchoSubstrings(String text) {
Set<String> st =new HashSet<>();
int n = text.length();
for (int len = 2; len <= n; len += 2) {
for (int i = 0; i + len <= n; ++i) {
int mid = i + len / 2;
if (text.substring(i, mid).equals(text.substring(mid, i + len))) {
st.add(text.substring(i, i + len));
}
}
}
return st.size();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution {
fundistinctEchoSubstrings(text: String): Int {
val st = mutableSetOf<String>()
val n = text.length
for (len in2..n step 2) {
for (i in0..n - len) {
val mid = i + len / 2if (text.substring(i, mid) == text.substring(mid, i + len)) {
st.add(text.substring(i, i + len))
}
}
}
return st.size
}
}
1
2
3
4
5
6
7
8
9
10
classSolution:
defdistinctEchoSubstrings(self, text: str) -> int:
st: set[str] = set()
n = len(text)
for l in range(2, n +1, 2):
for i in range(n - l +1):
mid = i + l //2if text[i:mid] == text[mid:i + l]:
st.add(text[i:i + l])
return len(st)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
impl Solution {
pubfndistinct_echo_substrings(text: String) -> i32 {
use std::collections::HashSet;
let n = text.len();
let s = text.as_bytes();
letmut st = HashSet::new();
for l in (2..=n).step_by(2) {
for i in0..=n - l {
let mid = i + l /2;
if&s[i..mid] ==&s[mid..i + l] {
st.insert(&text[i..i + l]);
}
}
}
st.len() asi32 }
}