Official Editorial (C++, Java)

Explanation

Lets consider a string with a non-reduced ratio $2D:2K$ and a substring with ratio $D:K$. If we take out the substring with ratio $D:K$, we are left with another substring with ratio $D:K$ ($2D-D:2K-K$), therefore making the original string able to be split. Thus, in order to "cut" a substring out of the original string, the reduced ratio of the substring must be the same as the reduced ratio of the original strng.

Note that the substrings must start from index $0$. If we pull a substring out of the middle of the string, it is harder to compute the ratio of the elements before it.

Keep track of the total number of 'D's and total number of 'K's. For each prefix, the ratio of $D:K$ in lowest terms is $\frac{D}{\gcd(D,K)}:\frac{K}{\gcd(D,K)}$. The solution to each prefix is how many times this reduced ratio has appeared so far plus one. We add one because the amount of times this reduced ratio appeared is the amount of splits, and the amount of pieces resulting from the splits is the splits plus one.

Implementation

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

Copy
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

int main() {

Copy
import java.io.*;
import java.util.*;

public class DilucKaeya {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int testNum = Integer.parseInt(read.readLine());

		StringBuilder ans = new StringBuilder();
		for (int t = 0; t < testNum; t++) {

Copy
from math import gcd

for _ in range(int(input())):
	input()
	k_num = 0
	d_num = 0
	max_pref_chunks = []
	pref_ratios = {}
	for c in input():
		if c == "D":