String Reduction

                            Solution in C :

In C++ :




#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<list>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<utility>
using namespace std;

int main() {
	string s;
	int T=0, res=0;
	int tab[3];

	cin >> T;

	for (int t = 0; t < T; t++) {
		s.clear();
		tab[0] = 0;
		tab[1] = 0;
		tab[2] = 0;
		res = 0;

		cin >> s;
		for (unsigned int i = 0; i < s.size(); i++) {
			if (s[i] == 'a') tab[0]++;
			else if(s[i] == 'b') tab[1]++;
			else if(s[i] == 'c') tab[2]++;
			else cerr << "dupa!" << endl;
		}

		sort(tab, tab+3);

		while (tab[1] > 0) {
			tab[2]--;
			tab[1]--;
			tab[0]++;
			sort(tab, tab+3);
		}

		cout << tab[2] << endl;
	}


	return 0;
}








In Java :





/*
 * Anand Oza
 * October 29, 2011
 */

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Solution {
	public static void main(String[] args) throws IOException {
		StreamTokenizer in = new StreamTokenizer(new InputStreamReader(
                     System.in));
		in.nextToken();
		int T = (int) in.nval;

		int ans;

		for (int test = 0; test < T; test++) {
			in.nextToken();
			char[] c = in.sval.toCharArray();
			int[] n = new int[3];
			for (int i = 0; i < c.length; i++)
				n[c[i] - 'a']++;
			int x = (n[0] + n[1]) * (n[1] + n[2]) * (n[2] + n[0]);
			if (x == 0)
				ans = c.length;
			else if ((n[0]+n[1])%2==0 && (n[1]+n[2])%2==0 && (n[2]+n[0])%2==0)
				ans = 2;
			else
				ans = 1;

			System.out.println(ans);
		}
	}
}








In C :





#include <stdio.h>
#include <string.h>

int min( int a, int b ) { return a < b ? a : b; }

int T, n;
char s[ 105 ];

int a[ 105 ][ 105 ];
int b[ 105 ][ 105 ];
int c[ 105 ][ 105 ];
int f[ 105 ][ 105 ];

int len, i, l, r, m;

int main()
{
  scanf( "%d", &T );
  
  while( T-- ) {
    scanf( "%s", s );
    n = strlen( s );

    for( i = 0; i < n; ++i ) {
      if( s[i] == 'a' ) a[i][i] = 1; else a[i][i] = 0;
      if( s[i] == 'b' ) b[i][i] = 1; else b[i][i] = 0;
      if( s[i] == 'c' ) c[i][i] = 1; else c[i][i] = 0;
      f[i][i] = 1;
    }
    
    for( len = 2; len <= n; ++len ) {
      for( l = 0; l+len <= n; ++l ) {
        r = l + len - 1;
        
        f[l][r] = f[l][r-1]+1;
        a[l][r] = b[l][r] = c[l][r] = 0;
        
        for( m = l; m < r; ++m ) {
          c[l][r] |= ( a[l][m] && b[m+1][r] || b[l][m] && a[m+1][r] );
          b[l][r] |= ( a[l][m] && c[m+1][r] || c[l][m] && a[m+1][r] );
          a[l][r] |= ( c[l][m] && b[m+1][r] || b[l][m] && c[m+1][r] );
          f[l][r] |= min( f[l][r], f[l][m] + f[m+1][r] );
        }

        
        if( a[l][r] || b[l][r] || c[l][r] ) f[l][r] = 1;
      }
    }
    
    printf( "%d\n", f[0][n-1] );
  }  

  return 0;
}








In Python3 :






__author__ = 'jonghewk'


def reductions(string):
    d = [0,0,0]
    for letter in string:
        if letter == 'a':
            d[0]+=1
        elif letter == 'b':
            d[1]+=1
        else:
            d[2]+=1

    while True:
        count =0
        for i in d:
            if i == 0:
                count+=1
        if count>=2:
            break

        d.sort(reverse=True)
        d[0]+=-1
        d[1]+=-1
        d[2]+=1

    sum = 0
    for i in d:
        sum+=i
    print(sum)


T = int(input())
cases = []
for i in range(T):
    cases.append(input().strip())

for w in cases:
    reductions(w)