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.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