Consider minimizing the number of transpositions to make a single array $a$ into a palindrome. We will assume for convenience that the number of 'G's in $a$ is an even number $2k$. The case where the number of 'G's is odd is essentially the same, except that you have to account for moving the middle 'G' to the center (and using $-1$ instead if the length of $a$ isn't odd).
Notice that we should never swap two adjacent 'G's as it doesn't change the array. It follows that the 'G's in $a$, relative to each other, stay in the same order as they were originally, meaning that to make $a$ into a palindrome, we want to match the first 'G' in $a$ with the last 'G', the second 'G' with the second to last 'G' and so on.
Therefore, for $1 \leq j \leq k$, let $a_j$ be the position of the $j$th 'G' in $a$ and let $b_j$ be the position counted from the end of the $j$th to last 'G' in $a$. The number of 'H's from the beginning to the $j$th 'G' is $a_j - j$, and the number of 'H's from the $j$th to last 'G' to the end is $b_j - j$. To make them match, we have to make the amount of 'H's between each and their respective ends the same, which requires $|(a_j - j) - (b_j - j)| = |a_j - b_j|$ transpositions.
Given this, to solve the problem in $\mathcal O(N^3)$ we can simply iterate over the $O(N^2)$ subarrays, and for each one calculate the values of $a_j, b_j$, then simply sum $|a_j - b_j|$ over all $j$ in $\mathcal O(N)$.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Palindromes {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
char[] lineup = in.readLine().toCharArray();
long answer = 0;
for (int l = 0; l < lineup.length; l++) {
for (int r = l; r < lineup.length; r++) {
long here = 0;
int a = l;
int b = r;
while (true) {
while (a < lineup.length && lineup[a] == 'H') {
a++;
}
while (b >= 0 && lineup[b] == 'H') {
b--;
}
if (a > b) {
break;
}
if (a == b) {
if ((l - r) % 2 == 0) {
here += Math.abs(a - ((l + r) / 2));
} else {
here = -1;
}
break;
}
here += Math.abs((a - l) - (r - b));
a++;
b--;
}
answer += here;
}
}
System.out.println(answer);
}
}
To optimize the runtime to $O(N^2)$, we can consider fixing the middle two 'G's, then calculating the answer for all corresponding subarrays more quickly. Say that the middle two 'G's we fixed are at positions $x < y$ in the entire array. The idea is that when we fix the middle two 'G's, every single 'G' is matched to the same other 'G': the $j$th 'G' to the left of $a_x$ is always matched to the $j$th 'G' to the right of $a_y$.
Following this idea, let's define $u_j$ to be the position of the $j$th 'G' to the left of position $x$, and $v_j$ to be the position of the $j$th 'G' to the right of $y$. Given that the subarray we are currently considering has endpoints $l \leq r$, the positions of these 'G's in the subarray are $u_j - l + 1$ counted from the beginning and $r - v_j + 1$ counted from the end respectively. Therefore, the number of transpositions needed to match them is
We can extend this idea to $F(s) = \sum_{j = 1}^k f_j(s)$, which is actually the number of transpositions needed for a subarray $a[l..r]$ with $l + r = s$ with $2k$ 'G's such that $a_x$ and $a_y$ are the middle 'G's. When we increase $s$ by $1$, $F(s)$ increases by $1$ for all $j$ such that $s \geq u_j + v_j$, and decreases by $1$ for other $j$. Let's quantify this difference as $d(s) = F(s + 1) - F(s)$. If we maintain $d(s)$, then we can update $F(s)$ to $F(s + 1)$ by simply adding $d(s)$. To then be able to calculate $F(s)$ for higher $s$, we need to be able to update $d(s)$ to $d(s + 1)$ as well, but to do that we simply need to add $2$ for each $j$ such that $u_j + v_j = s + 1$; we can do this easily by simply storing an array $e(s)$ that counts the amount of $j$ such that $u_j + v_j = s$, and calculating $d(s + 1)$ as $d(s) + 2e(s + 1)$.
Therefore, our algorithm will be as follows. For each adjacent pair of 'G's $a_x$ and $a_y$ (there can be 'H's between them but no 'G's), initialize an array $e$ to be all $0$s. We will then compute the answers for subarrays centered at $a_x, a_y$ in phases. For each $k$ starting from $1$, we update $e$ by adding $1$ to $e(u_k + v_k)$. Then, we compute the answers for all subarrays $a[l..r]$ such that $u_{k + 1} < l \leq u_k$ and $v_k \leq r < v_{k + 1}$. Starting with $l = u_k$ and $r = v_k$, we maintain the values of $F(l + r)$ and $d(l + r)$. We repeatedly increase $r$ by $1$, updating $F(l + r)$ and $d(l + r)$ in constant time as we explained above, and importantly adding $F(l + r)$ to our overall answer, until we reach $r = v_{k + 1}$, at which we decrease $r$ back down to $v_k$ in a similar manner. We then decrease $l$ by $1$, and repeat, until we reach $l = u_{k + 1}$. At that point, we've calculated the contributions of all the subarrays that we wanted to.
In terms of runtime, we aren't guaranteed that a single step of fixing the middle two 'G's takes $\mathcal O(N)$ -- even a single phase could take $O(N^2)$ -- but overall, we only take constant time to compute the answer for each subarray, meaning that the overall runtime is $O(N^2)$. We also need to initialize the array $e$ which needs $O(N)$ space, but since we fix the middle two 'G's less than $N$ times, this is also $O(N^2)$.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Palindromes {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
char[] lineup = in.readLine().toCharArray();
int[] gs = new int[lineup.length];
int amountG = 0;
for (int j = 0; j < lineup.length; j++) {
if (lineup[j] == 'G') {
gs[amountG] = j;
amountG++;
}
}
long answer = 0;
for (int leftCenter = 0; leftCenter < amountG; leftCenter++) {
for (int rightCenter = leftCenter; rightCenter <= leftCenter + 1 && rightCenter < amountG; rightCenter++) {
long[] e = new long[2 * lineup.length];
long d = 0;
long F = 0;
for (int k = 0; leftCenter - k >= 0 && rightCenter + k < amountG; k++) {
int uk = gs[leftCenter - k];
int uk1 = leftCenter - k == 0 ? -1 : gs[leftCenter - (k + 1)];
int vk = gs[rightCenter + k];
int vk1 = rightCenter + (k + 1) == amountG ? lineup.length : gs[rightCenter + (k + 1)];
if (uk < vk) {
e[uk + vk] += 2;
d++;
}
for (int l = uk; l > uk1; l--) {
for (int r = vk; r < vk1; r++) {
if (leftCenter == rightCenter) {
if ((r - l) % 2 == 0) {
answer += F + ((long) Math.abs(((r + l) / 2) - gs[leftCenter]));
} else {
answer--;
}
} else {
answer += F;
}
F += d;
d += e[l + r + 1];
}
for (int r = vk1; r > vk; r--) {
d -= e[l + r];
F -= d;
}
d -= e[l + vk];
F -= d;
}
for (int r = vk; r < vk1; r++) {
F += d;
d += e[uk1 + r + 1];
}
}
}
}
System.out.println(answer);
}
}