ある文字列 \(s\) が嬉しい列となる条件を考えましょう。
当たり前ですが、並べ替えた後の文字列が同じ列を \(2\) 度繰り返した列になるためには、 \(s\) に全ての文字が偶数回含まれている必要があります。
逆に、これを満たしていれば必ず並べ替えて同じ列を \(2\) 度繰り返すようにできます。(全ての文字を前半と後半に半分ずつ分けて、それぞれを昇順に並べると同じ文字列を \(2\) 度繰り返すことになります)

では、そのような連続部分文字列がいくつあるか数えていきましょう。
先頭から \(i\) 文字 ( \(0 \le i \le |S|\) ) に \(x\) が出現した回数を \(2\) で割った余りを \(R_{i,x}\) とします。

\(S=\) 20230322 のとき

       R_{i,x} ( x=0,1,...,9 )
i = 0  0000000000
i = 1  0010000000
i = 2  1010000000
i = 3  1000000000
i = 4  1001000000
i = 5  0001000000
i = 6  0000000000
i = 7  0010000000
i = 8  0000000000

このとき、

• \(R_i = R_j\) ( \(i<j\) ) であれば \(S\) の \(i+1\) 文字目から \(j\) 文字目までを抜き出した列が嬉しい列
• \(R_i \neq R_j\) ( \(i<j\) ) であれば \(S\) の \(i+1\) 文字目から \(j\) 文字目までを抜き出した列が嬉しい列でない

ことが示せます。証明は以下の通りです。

• (1つ目) … 全ての文字について、 \(i\) 文字目時点と \(j\) 文字目時点で偶奇が変わっていないことから、全ての文字が偶数回含まれることが示せます。
• (2つ目) … ある文字について、 \(i\) 文字目時点と \(j\) 文字目時点で偶奇が変わっていることから、その文字が奇数回含まれることが示せます。

よって、 \(R_i\) が等しい \(i\) のうちから相異なる \(2\) つを選べば、その組に嬉しい列である区間が対応することになります。
この選び方を \(R_i\) がとりうる \(2^{10}\) 通り足し上げてもよいです(実装例1)し、組の後ろ側の要素を見る際に前側の要素として取りうるものが何個あるかを足し上げてもよいです(実装例2)。

実装例1 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  string s;
  cin >> s;
  map<vector<int>,long long> mp;
  vector<int> cnt(10,0);
  mp[cnt]++;
  for(auto &nx : s){
    cnt[nx-'0']++;
    cnt[nx-'0']%=2;
    mp[cnt]++;
  }
  long long res=0;
  for(auto &nx : mp){
    long long x=nx.second;
    res+=(x*(x-1))/2;
  }
  cout << res << "\n";
  return 0;
}

実装例2 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  string s;
  cin >> s;
  int flag=0;
  vector<long long> bk(1024,0);
  bk[0]++;
  long long res=0;
  for(auto &nx : s){
    flag^=(1<<(nx-'0'));
    res+=bk[flag];
    bk[flag]++;
  }
  cout << res << "\n";
  return 0;
}