Twin Strings
Problem
You are given a string \(S\) of length \(N\). A string is called twin if the characters of the string can be split into two groups such that the occurrence of each character is equal in both groups.
Find the number of twin substrings of \(S\).
Input Format:
- The first line contains an integer \(T\), denoting the number of test cases.
- The first line of each test case contains an integer \(N\), denoting the length of the string \(S\).
- The second line of each test case contains the string \(S\).
Output Format:
For each test case, print the number of twin substrings of \(S\).
Constraints:
\(1 <= T <= 10\)
\(1 <= N <= 10^5\)
\(S \) contains lower-case English letters
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation
First test case:-
Substrings \(cc, bccb, abccba\) are twin as they can divide into \((c,c), (bc,cb)\) and \((abc,cba)\) respectively. Hence, the answer is \(3\).
Second test case:-
Substring \(dd\) is twin as they can divide into \((d, d)\). Hence, the answer is \(1\).
