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).

Examples

Example 1

1
2
3

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

Example 2

1
2
3

Input: text = "leetcodeleetcode"
Output: 2
Explanation: The 2 substrings are "ee" and "leetcodeleetcode".

Constraints

  • 1 <= text.length <= 2000
  • text has only lowercase English letters.

Solution

Method 1 – Rolling Hash (Rabin-Karp)

Intuition

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.

Approach

  1. Iterate over all possible even lengths l (from 2 to n, step 2).
  2. For each starting index i, check the substring text[i:i+l].
  3. Use rolling hash to compare the first half and the second half of the substring.
  4. If they match, add the substring to a set to ensure uniqueness.
  5. Return the size of the set.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
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();
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func distinctEchoSubstrings(text string) int {
    st := map[string]struct{}{}
    n := len(text)
    for l := 2; l <= n; l += 2 {
        for i := 0; i+l <= n; i++ {
            mid := i + l/2
            if text[i:mid] == text[mid:i+l] {
                st[text[i:i+l]] = struct{}{}
            }
        }
    }
    return len(st)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int distinctEchoSubstrings(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

class Solution {
    fun distinctEchoSubstrings(text: String): Int {
        val st = mutableSetOf<String>()
        val n = text.length
        for (len in 2..n step 2) {
            for (i in 0..n - len) {
                val mid = i + len / 2
                if (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

class Solution:
    def distinctEchoSubstrings(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 // 2
                if 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 {
    pub fn distinct_echo_substrings(text: String) -> i32 {
        use std::collections::HashSet;
        let n = text.len();
        let s = text.as_bytes();
        let mut st = HashSet::new();
        for l in (2..=n).step_by(2) {
            for i in 0..=n - l {
                let mid = i + l / 2;
                if &s[i..mid] == &s[mid..i + l] {
                    st.insert(&text[i..i + l]);
                }
            }
        }
        st.len() as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    distinctEchoSubstrings(text: string): number {
        const st = new Set<string>();
        const n = text.length;
        for (let l = 2; l <= n; l += 2) {
            for (let i = 0; i + l <= n; ++i) {
                const mid = i + l / 2;
                if (text.slice(i, mid) === text.slice(mid, i + l)) {
                    st.add(text.slice(i, i + l));
                }
            }
        }
        return st.size;
    }
}

Complexity

  • ⏰ Time complexity: O(n^3), because for each substring (O(n^2)), we compare two halves (O(n)).
  • 🧺 Space complexity: O(n^2), for storing all possible substrings in the set.