leetcode 1316 - Distinct Echo Substrings

https://leetcode.com/problems/distinct-echo-substrings/
https://leetcode.com/problems/distinct-echo-substrings/discuss/478854/C%2B%2B-DP-solution-O(N2)-with-explanation

Return the number of distinct non-empty substrings of text that can be written as the concatenation of some string with itself.

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int distinctEchoSubstrings(string text) {
unordered_set<string> distinct;
int size = text.size();

vector<vector<int>> dp(size+1, vector<int>(size+1, 0));

for (int j = size - 1; j > 0; j--) {
for (int i = j - 1; i >= 0; i--) {
if (text[i] == text[j])
dp[i][j] = dp[i+1][j+1] + 1;

if (dp[i][j] >= j - i)
distinct.insert(text.substr(i, j-i));
}
}

return distinct.size();
}
};