# Count balanced substring

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.Scanner;
import java.util.Set;

public class BalancedStrings {
static int  returnbalance(String input){
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()));
}

}

}

• Is this a programming-challenge that is published online? If so, please cite the source. – 200_success May 13 '15 at 1:12
• This is practice question Earlier i shared the link but its not accessible if you don't have login. – Mohan Raj May 13 '15 at 3:43

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 ?

A substring is a string that appears unbroken within another string. So for example, the provided answers are substrings

cc       ab|cc|ba
bccb     a|bccb|a
abccba   |abccba|


The other balanced substrings "aa", "bb", "cc", "abba", "acca", and "cbbc" are not substrings but a subset (w/ duplicates) of the characters in the original string.

The main thing to note is that order of the characters as well as the count of each characters matters.

@OP: Beware not to confuse substring with Subsequence

• For input aabb : Balanced substring are "aa" , "bb" , "aabb" As per above explanation then aa and bb should not be counted right? – Mohan Raj May 13 '15 at 3:45
• Let's stick with the original example "abccba". Why are "aa" and "bb" not substrings of "abccba"? It is because the string "aa" and "bb" do not appear UNBROKEN in the original string. Yes, the string "abccba" does contain two 'a's and two 'b's, but that does not automatically mean "aa" or "bb" is a substring of "abccba". – FriedSaucePots May 13 '15 at 13:24
• Pleas see original post for more resources on substring vs subsequence – FriedSaucePots May 13 '15 at 13:29
• aabb is the another input given and the output is 3 as per the site because of the first input and output i got confused. – Mohan Raj May 18 '15 at 4:23