Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerRank String Reduction problem solution

YASH PAL, 31 July 2024

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.

HackerRank String Reduction problem solution

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

  return 0;
}

Algorithms coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes