Official Analysis

Explanation

The greedy approach is implemented below. We are going to initialize two strings (in this case, hash values) - one built with the $i'$th character and the other with its $n - i - 1$'th complement. We will loop from left to right, adding characters one at a time to their respective strings until the left string is the same as the right string, in which we can create two partitions. To check the equality of these strings, we will use string hashing.

Implementation

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

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

const ll P = 69421;
const ll M = 1e9 + 9;

int main() {
	int tc;
	cin >> tc;