PROBLEM LINK:
Setter : Bhavyesh Desai
Tester : Rahul Dugar
Editorialist : Rajarshi Basu
DIFFICULTY:
Easy
PREREQUISITE:
Bitmasks
PROBLEM:
The notorious hacker group “Sed” managed to obtain a string S from their secret sources. The string contains only lowercase English letters along with the character ‘?’.
A substring of S is a contiguous subsequence of that string. For example, the string “chef” is a substring of the string “codechef”, but the string “codeh” is not a substring of “codechef”.
A substring of S is good if it is possible to choose a lowercase English letter C such that the following process succeeds:
- Create a string R, which is a copy of the substring, but with each ‘?’ replaced by the letter c. Note that all occurrences of ‘?’ must be replaced by the same letter.
- For each lowercase English letter:
- Compute the number of times it occurs in S and the number of times it occurs in R; let’s denote them by A and B respectively. The ‘?’ characters in the original string S are ignored when computing A.
- Check the parity of A and B. If they do not have the same parity, i.e. one of them is even while the other is odd, then this process fails.
- If the parities of the number of occurrences in S and R are the same for each letter, the process succeeds.
For different substrings, we may choose different values of C.
Help Sed find the number of good substrings in the string S.
Constraints
- 1 \le T \le 10^5
- 1 \le S \le 10^5
- S contains only lowercase English letters (‘a’ through ‘z’) and ‘?’
- the sum of |S| over all test cases does not exceed 10^5
BRIEF EXPLANATION:
sm0l s0lution
Essentially, we check for all substrings. We keep track of the prefix parity using a bitmask. For every right index, we essentially want to count possible left indices. That can be done by just getting the number of prefix parity bitmasks that, when xorred with the current prefix bitmask, gives the bitmask of the parity of characters of entire string.
EXPLANATION:
Observation 1
First, we can represent all the parity information using a simple bitmask. One for each character, and one extra for parity of question marks.
Observation 2
Bitmasks also give us another advantage — we can xor them, which is commutative. Hence, we can keep track of prefix parities.
Observation 3 - Final Solution
Let the prefix bitmasks be represented by bitmask[i] meaning parity of all characters in s[1…i].
Checking for even occurances of ?
For checking substring with even number of ?, we just check how many occurances of the same bitmask[i] have occurred before …. but not exactly. What should we do?
Details
We should actually query with bitmask[i] \oplus bitmask[n] since we want our bitmask to match that of the entire string.
Checking for odd occurances of ?
Here, try to replace which each character (think how the bitmask to query changes, also remember to flip the bit representing the ?).
Intuition on why the methods are different
Essentially, the reason is even if we tried replacing in the bitmask while doing for even occurances, it would have given the same bitmask since we would not be changing any parities (even occurances of ? remember?). Hence, we would repeatedly count the same bitmasks again and again, which is overcounting. This will not happen in the odd case.
See Codes for exact implementation details.
SOLUTION:
Tester’s Code
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int suss=0;
void solve() {
string s=readStringLn(1,100000);
suss+=sz(s);
assert(suss<=100000);
int btc=0;
for(char i:s) {
assert(('a'<=i&&i<='z')||i=='?');
if(i!='?')
btc^=(1<<(i-'a'));
}
map<int,int> socool;
int xooo=0;
socool[0]=1;
int ans=0;
for(char i:s) {
if(i!='?')
xooo^=(1<<(i-'a'));
else
xooo^=(1<<26);
ans+=socool[xooo^btc];
for(int i=0; i<26; i++)
ans+=socool[xooo^(1<<26)^(1<<i)^btc];
socool[xooo]++;
}
cout<<ans<<endl;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(7);
int t=readIntLn(1,100000);
fr(i,1,t)
solve();
assert(getchar()==EOF);
#ifdef rd
// cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}