Scatter Palindrome

Problem For a given string, determine for each queried prefix/substring whether its characters can be rearranged into a palindrome (a "scatter palindrome").

Input / Output

• Input: string s (and optionally query ranges).
• Output: boolean per prefix/substring (or a count of scatter-palindromic ones).

Constraints

• |s| up to 10^5 with many queries — per-query recounting is too slow; precompute.

Example

• "aab" prefixes: "a" ✓, "aa" ✓, "aab" ✓ (aba). "abc" → "ab", "abc" ✗.

Expected approach

• Rearrangeable into a palindrome ⇔ at most one character has odd frequency. Encode parity as a 26-bit mask; prefix masks m[i] are computable in one pass (XOR the char bit). A prefix is scatter-palindromic iff popcount(m[i]) <= 1; a substring (l, r] iff popcount(m[r] XOR m[l]) <= 1. O(n + queries) time. The bitmask parity trick is the point — state it explicitly.