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.

Function Description

Complete the stringReduction function in the editor below. It must return an integer that denotes the length of the shortest string obtainable.

stringReduction has the following parameter:
– s: a string

Input Format

The first line contains the number of test cases t.

Each of the next  lines contains a string  to process.

HackerRank String Reduction 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))

String Reduction 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("%dn", process(str));
  }

  return 0;
}