Problem: perfectly_balanced_ch1 (2022 round2)

**Note: This is the easier version of [Chapter 2](https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-2/problems/A2). This version involves a string, but chapter 2 involves an array of integers that can change with updates.**

A string is *perfectly balanced* if its length is even, and the first half of the string can be shuffled to make the string a palindrome. For example, "`abab`" and "`dood`" are perfectly balanced, but "`racecar`" and "`doodad`" are not.

A string is *almost perfectly balanced* if you can delete exactly one character from it to make it perfectly balanced. Some examples are  "`classical`", "`intelligent`", and "`www`".

{{PHOTO_ID:1262846811180772|WIDTH:700}}

You are given a larger template string \(S\), and \(Q\) substrings, the \(i\)th of which is \(S_{L_i..R_i}\). For how many of these \(Q\) queries is the substring almost perfectly balanced?


# Constraints

\(1 \le T \le 90\)
\(1 \le |S| \le 10^6\)
\(S_i \in\) {'`a`', ..., '`z`'}
\(1 \le Q \le 10^6\)
\(1 \le L_i \le R_i \le |S|\)

The sum of \(|S|\) across all test cases is at most \(4{,}000{,}000\).
The sum of \(Q\) across all test cases is at most \(4{,}000{,}000\).


# Input Format

Input begins with a single integer \(T\), the number of test cases. For each test case, there is first a line containing a single template string \(S\). Then, there is a line containing a single integer \(Q\). Then, \(Q\) lines follow, the \(i\)th of which contains two space-separated integers \(L_i\) and \(R_i\).


# Output Format

For the \(i\)th test case, output a single line containing `"Case #i: "`, followed by a single integer: the number of queries which are an almost perfectly balanced substring.


# Sample Explanation

In the first case, the template string is "`singingbanana`".

For the first query, the substring is "`banan`". You can delete the `"b"` to get "`anan`" then reorder the first half of the string to get `"naan"`, which is a palindrome. Thus, "`banan`" is an almost perfectly balanced substring.

For the second query, the substring is "`anana`". You can delete the second "`a`" to get "`anna`", which is a palindrome. Thus, "`anana`" is an almost perfectly balanced substring.

For the third query, the substring is "`ban`". You cannot delete any character to get an almost perfectly balanced substring.

For the fourth query, the substring is "`nan`". You can delete the "`a`" to get "`nn`", which is a palindrome. Thus, "`nan`" is an almost perfectly balanced substring.

For "`singing`", you can create "`gniing`".

In the second test case, the first, second, and third queries are almost perfectly balanced substrings, but the fourth is not.

In the third test case, the first, second, third, and fourth queries are almost perfectly balanced substrings, but the fifth and sixth are not.


Sample input:
3
singingbanana
5
8 12
9 13
8 10
10 12
1 7
prepareintelligentopinion
4
1 7
8 18
19 25
12 13
phpservers
6
1 3
4 10
1 3
2 2
3 5
1 10


Sample output:
Case #1: 4
Case #2: 3
Case #3: 4


Solution: The definition of a perfectly balanced string can be simplified to "any even-length string where the character frequencies in the first half are the same as the second half."

Since there are only \(26\) letters, we can precompute a prefix-sum array \(P_c\) of frequencies for each letter \(c\), where \(P_c[i]\) stores the frequency of letter \(c\) in \(S_{1..i}\). This will let us obtain the frequency of any letter \(c\) in any substring \(S_{a..b}\) in constant time, using \(P_c[b] - P_c[a-1]\).

For each query substring \(S_{l..r}\), there are two possible split-points to check in the middle. Let \(m = \lfloor(l + r)/2\rfloor\). We can first compare the frequencies of \(S_{l..(m-1)}\) with \(S_{m..r}\), then compare the frequencies of \(S_{l..m}\) with \(S_{(m+1)..r}\). If in either comparison we find that the frequencies differ by exactly \(1\) letter between the two sides, then \(S_{l..r}\) is almost perfectly balanced.

[See David Harmeyer's solution video here.](https://www.youtube.com/watch?v=w65VekVkuHA)


Code: #include <iostream>
#include <vector>
using namespace std;

using vi = vector<int>;

bool almost_perfect(const vi &big, const vi &small) {
  int diff = 0;
  for (int c = 0; c < 26; c++) {
    if (big[c] < small[c]) {
      return false;
    }
    diff += big[c] - small[c];
  }
  return diff == 1;
}

int solve() {
  string S;
  cin >> S;
  vector<vi> pre(S.size() + 1, vi(26));
  for (int i = 1; i <= (int)S.size(); i++) {
    pre[i] = pre[i - 1];
    pre[i][S[i - 1] - 'a']++;
  }
  int Q;
  cin >> Q;
  int ans = 0;
  for (int i = 0, l, r; i < Q; i++) {
    cin >> l >> r;
    --l, --r;
    if ((r - l + 1) % 2 == 0) {
      continue;
    }
    auto get_freqs = [&](int l, int r) {
      vi res;
      for (int c = 0; c < 26; c++) {
        res.push_back(pre[r + 1][c] - pre[l][c]);
      }
      return res;
    };
    int m = (l + r) / 2;
    if (almost_perfect(get_freqs(l, m), get_freqs(m + 1, r)) ||
        almost_perfect(get_freqs(m, r), get_freqs(l, m - 1))) {
      ans++;
    }
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}