Chandan got bored playing with the arrays all the time. Therefore he has decided to buy a string \$S\$ consists of \$N\$ lower case letters. Once he purchased the string, He starts formulating his own terminologies over his string \$S\$. Chandan calls a string str A Balanced String if and only if the characters of the string str can be paritioned into two multisets \$M_1\$ and \$M_2\$ such that \$M_1=M_2\$ .
For example:
Strings like "abccba" , "abaccb" , "aabbcc" are all balanced strings as their characters can be partitioned in the two multisets \$M_1\$ and \$M2\$ such that \$M_1=M_2\$.
$$M1 = {a,b,c} \\ M2 = {c,b,a}$$
whereas strings like ababab , abcabb are not balanced at all.
Chandan wonders how many substrings of his string \$S\$ are Balanced Strings? Chandan is a little guy and do not know how to calculate the count of such substrings.
For input "abccba" Balanced substring are "cc" , "bccb" , "abccba" ie count=3 (Provided as per problem statement discussion) But I guess "aa", "bb", "cc", "abba", "acca", "cbbc" are also balanced sub string for the same input which makes count=6 Any wrong in my interpretation ?
Program
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Scanner;
import java.util.Set;
public class BalancedStrings {
static int returnbalance(String input){
HashMap<Character, Integer> characters=new LinkedHashMap<>();
int count=0;
Character c=null;
for(int i=0;i<input.length();i++){
c=input.charAt(i);
if(characters.containsKey(c)==true){
count=characters.get(c);
characters.put(c, count+1);
}
else
characters.put(c,1);
}
int countunique=0;
Set<Character> s=characters.keySet();
for(Character cc:s){
count=characters.get(cc);
if(count%2==0)
countunique++;
}
if(countunique!=s.size())
return 0;
Object[] sar= s.toArray();
int len=0;
for(int i=sar.length-1;i>=0;i--){
len=len+i;
}
return len+countunique;
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int numberOfInputs=in.nextInt();
in.nextLine();
for(int i=0;i<numberOfInputs;i++){
System.out.println(BalancedStrings.returnbalance(in.nextLine()));
}
}
}
