Official Editorial (C++)

Implementation

Note this is a bit different from the implementation outlined in the official editorial. This loops over the start and end of the substrings rather than the length first.

Time Complexity: $\mathcal{O}(N^2)$

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(false);
	string s;
	cin >> s;
	int n = s.length();

	// dp[i][j] = number of palidrome substrings in [i,j]