HackerRank String Reduction problem solution

In this HackerRank String Reduction problem solution, we have given a string consisting of the letters a, b and c and we need to take any two adjacent distinct characters and replace them with the third character and then find the shortest string obtainable through this operation.

Problem solution in Python.

#!/usr/bin/py
# Head ends here
dyn = {}

def stringReduction(a):
    #print(a)
    if a in dyn.keys():
        return dyn[a]
    if len(a) == 1:
        dyn[a] = 1
        return 1
    ans = 101
    ko = 0
    for i in range(len(a) - 1):
        if a[i] != a[i + 1]:
            b = list(a)
            b[i + 1] = ({'a', 'b', 'c'} - {b[i], b[i + 1]}).pop()
            del b[i]
            ans = min(ans, stringReduction(''.join(b)))
            ko += 1
            if ko > 1:
                break
    if ko == 0:
        ans = len(a)
    dyn[a] = ans
    return ans
# Tail starts here
if __name__ == '__main__':
    t = int(input())
    for i in range(0,t):
        a=input()
        print(stringReduction(a))

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String...args) {
		Scanner sc = new Scanner(System.in);
		int t = Integer.parseInt(sc.nextLine().trim());
		for (int k = 0; k < t; k++) {
			String s = sc.nextLine();

			int[] a = new int[3];
			for (int i = 0; i < s.length(); i++) {
				if (s.charAt(i) == 'a') a[0]++;
				if (s.charAt(i) == 'b') a[1]++;
				if (s.charAt(i) == 'c') a[2]++;
			}
			
			while (true) {
				int c = a[0] + a[1] + a[2];
				if (a[0] == c || a[1] == c || a[2] ==c) 
					break;
				
				if (a[0] <= a[1] && a[0] <= a[2]) {
					a[0]++;
					a[1]--;
					a[2]--;
				} else 
					if (a[1] <= a[0] && a[1] <= a[2]) {
						a[1]++;
						a[0]--;
						a[2]--;
					} else
						if (a[2] <= a[0] && a[2] <= a[1]) {
							a[2]++;
							a[0]--;
							a[1]--;
						};
				
				
			}
			
			System.out.println(a[0] + a[1] + a[2]);
			
		}
		sc.close();
	}
}

Problem solution in C++.

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <sstream>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <cctype>
#include <limits>
#include<ctime>

using namespace std;

const double EPS = 1e-9;
const long long  INF = 1000000000000000000;

typedef pair<int, int> PII;
typedef pair<double,double> PDD;
typedef vector<long long> VLL;
typedef vector<int> VI;

#define FOR(i,a,b) for (int _n(b), i(a); i < _n; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
#define REP(i,n) FOR(i,0,n)

#define UNIQUE(v) SORT(v), v.erase(unique(v.begin(),v.end()),v.end())
#define SORT(c) sort((c).begin(),(c).end())
#define ll long long

map<string, int> h;

string third(char f , char s)
{
	if (f+s == 'a' + 'b') return "c";
	if (f+s == 'a' + 'c') return "b";
	return "a";
}

bool ok;
int ret ;

int simply(string s )
{
	if (!ok) return ret;
	int n = s.size();
	if (n==1)
	{
		ok = false;
		ret= 1;
		return ret;
	}
	if (n==2)
	{
		ok = false;
		if (s[0]==s[1]) ret=2; else ret = 1;
		return ret;
	}
	int res = n;
	REP(i,n)
	{
		if (i<n-1 && s[i]!=s[i+1])
		{
			string t = s.substr(0,i) + third(s[i], s[i+1]);
			if (i+2<n) t+= s.substr(i+2,n-i-2);
			res = min(res , simply(t));
			if (res == 1)
			{
				ok = false;
				ret= 1;
				return ret;
			}
		}
	}
	return res;
}

int main()
{
#ifdef LocalHost
        freopen("input.txt","r",stdin);
#endif
		
		int T;
		string s;
		cin>>T;

		REP(i,T)
		{
			cin>>s;
			ok = true;
			ret = s.size();
			cout<<simply(s)<<endl;
		}

#ifdef LocalHost
        cout<<endl<<endl<<"TIME: "<<clock()<<endl;
#endif

}

Problem solution in C.

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


typedef struct{
  int l;
  char c;
}var;

var arr[100][100];

var compare(var a, var b){
  var ret;

  if(a.c == b.c){
    ret.l = a.l + b.l;
    ret.c = a.c;
    return  ret;
  }
   
  if(a.l % 2 == 0){
    if(b.l % 2 == 0){
      ret.l = 2;
      ret.c = (a.l < b.l) ? a.c : b.c;
    }
    else{
      ret.l = 1;
      ret.c = b.c;
    }
  }
  else{
    if(b.l % 2 == 0){
      ret.l = 1;
      ret.c = a.c;
    }
    else{
      ret.l = 1;
      ret.c = 'a' + 'b' + 'c' - a.c - b.c;
    }
  }

  return ret;
}

int process(char *str){
  int len = strlen(str);

  int i, j;
  for(i=0; i<len; i++){
    arr[i][i].l = 1;
    arr[i][i].c = str[i];
  }

  for(i=1; i<len; i++){
    for(j=0; j<len-i; j++){
      int k;
      var min; min.l = 1000;
      for(k=j; k<j+i; k++){
	var ret = compare(arr[j][k], arr[k+1][i+j]);
	if(ret.l < min.l)
	  min = ret;
      }

      arr[j][j+i] = min;
    }
  }

  return arr[0][len-1].l;
}

int main(){
  int T, i;
  scanf("%d", &T);

  char *str = (char *)malloc(101*sizeof(char));
  for(i=0; i<T; i++){
    scanf("%s", str);
    printf("%d\n", process(str));
  }

  return 0;
}