In this post, we will solve HackerRank String Reduction Problem Solution.
Given a string consisting of the letters a. b and c, we can perform the following operation:
Take any two adjacent distinct characters and replace them with the third character. Find the shortest string obtainable through applying this operation repeatedly.
For example, given the string aba we can reduce it to a 1 character string by replacing ab with c and ca with b: aba → ca → b.
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 t lines contains a string 8 to process.
Output Format
For each test case, print the length of the resultant minimal string on a new line.
Sample Input
3
cab
bcab
ccccc
Sample Output
2
1
5Explanation
For the first case, there are two solutions: cab→ cc or cab→ bb. For the second case, one optimal solution is: bcab→ aab → ac→ b. For the third case, no operations can be performed so the answer is 5.
String Reduction C Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include<stdio.h>
#include<string.h>
main()
{
int cases;
scanf("%d",&cases);
while(cases-- != 0)
{
char strng[100];
scanf("%s", strng);
int i, arr[3];
arr[0] = 0;
arr[1] = 0;
arr[2] = 0;
for(i = 0 ; i < strlen(strng) ; i++)
{
if(strng[i] == 'a')
arr[0] += 1;
else
{
if(strng[i] == 'b')
arr[1] += 1;
else
arr[2] += 1;
}
}
int min;
while(1)
{
min = arr[0];
int count = 0;
if(min == 0)
count = 1;
for(i = 1 ; i < 3 ; i++)
{
if(arr[i] < min)
min = arr[i];
if(arr[i] == 0)
count += 1;
}
if(count == 2)
break;
count = 0;
for(i = 0 ; i < 3 ; i++)
{
if(count == 0 && arr[i] == min)
{
arr[i] += 1;
count += 1;
}
else
arr[i] -= 1;
}
}
for(i = 0 ; i < 3 ; i++)
{
if(arr[i] != 0)
{
printf("%d\n",arr[i]);
break;
}
}
}
}String Reduction C++ Solution
#include <iostream>
#include <string>
#include <limits>
#include <cassert>
using namespace std;
const int maxStringLength = 100;
const int numLetters = 3;
// i.e. "minLetterCountInRange[i][j][x]": in the substring s[i..j],
// what is the smallest number of letter x we can reduce the substring to?
int minLetterCountInRange[maxStringLength][maxStringLength][numLetters];
int calcMinLetterCountInRange(const string& s, int rangeBegin, int rangeEnd, int letter)
{
//assert(rangeBegin >= 0);
//assert(rangeEnd >= rangeBegin && rangeEnd < s.size());
//assert(letter >= 0 && letter < numLetters);
#if 0
string dbgSubstring;
for (const auto letter : s.substr(rangeBegin, rangeEnd - rangeBegin + 1))
{
dbgSubstring += 'a' + letter;
}
cout << "rangeBegin: " << rangeBegin << " rangeEnd: " << rangeEnd << " letter:" << letter << " substring:" << dbgSubstring << endl;
#endif
const int memoisedResult = minLetterCountInRange[rangeBegin][rangeEnd][letter];
if (memoisedResult != -1)
{
//cout << "Returning memo-ised: " << minLetterCountInRange[rangeBegin][rangeEnd][letter] << endl;
return memoisedResult;
}
if (rangeBegin == rangeEnd)
{
//cout << "single letter:" << s[rangeBegin] + 'a' << endl;
return (s[rangeBegin] == letter) ? 1 : 0;
}
bool allSameLetter = true;
for (int i = rangeBegin + 1; i <= rangeEnd; i++)
{
if (s[i] != s[i - 1])
{
allSameLetter = false;
break;
}
}
if (allSameLetter)
{
//cout << "All same letter:" << (s[rangeBegin] == letter ? s.size() : 0) << endl;
return s[rangeBegin] == letter ? rangeEnd - rangeBegin + 1 : 0;
}
int minOfLetter = std::numeric_limits<int>::max();
for (int i = rangeBegin + 1; i <= rangeEnd; i++)
{
for (int leftLetter = 0; leftLetter < numLetters; leftLetter++)
{
for (int rightLetter = 0; rightLetter < numLetters; rightLetter++)
{
const int leftRangeBegin = rangeBegin;
const int leftRangeEnd = i - 1;
const int minLeftLetterCountOnLeft = calcMinLetterCountInRange(s, leftRangeBegin, leftRangeEnd, leftLetter);
// Memo-ise.
minLetterCountInRange[leftRangeBegin][leftRangeEnd][leftLetter] = minLeftLetterCountOnLeft;
if (minLeftLetterCountOnLeft == 0)
continue;
const int rightRangeBegin = i;
const int rightRangeEnd = rangeEnd;
const int minRightLetterCountOnRight = calcMinLetterCountInRange(s, rightRangeBegin, rightRangeEnd, rightLetter);
// Memo-ise.
minLetterCountInRange[rightRangeBegin][rightRangeEnd][rightLetter] = minRightLetterCountOnRight;
if (minRightLetterCountOnRight == 0)
continue;
if (leftLetter == rightLetter)
{
if (leftLetter == letter && rightLetter == letter)
minOfLetter = min(minOfLetter, minLeftLetterCountOnLeft + minRightLetterCountOnRight);
}
else
{
const bool leftLetterOdd = ((minLeftLetterCountOnLeft % 2) == 1);
const bool rightLetterOdd = (minRightLetterCountOnRight % 2) == 1;
if (!leftLetterOdd && !rightLetterOdd)
{
if (leftLetter == letter || rightLetter == letter)
{
minOfLetter = min(minOfLetter, 2);
}
}
else if (leftLetterOdd && rightLetterOdd)
{
const int otherLetter = 3 - (leftLetter + rightLetter);
if (otherLetter == letter)
{
minOfLetter = min(minOfLetter, 1);
}
}
else if (leftLetter == letter && leftLetterOdd)
{
minOfLetter = min(minOfLetter, 1);
}
else if (rightLetter == letter && rightLetterOdd)
{
minOfLetter = min(minOfLetter, 1);
}
//assert(otherLetter >= 0 && otherLetter < numLetters && otherLetter != leftLetter && otherLetter != rightLetter);
}
if (rangeBegin == 0 && rangeEnd == s.size() - 1 && minOfLetter == 1)
{
//cout << "leftLetter: " << leftLetter << " rightLetter: " << rightLetter << " i: " << i << endl;
}
}
}
}
// Memo-ise.
if (minOfLetter == std::numeric_limits<int>::max())
minOfLetter = 0;
minLetterCountInRange[rangeBegin][rangeEnd][letter] = minOfLetter;
return minOfLetter;
}
void bruteForce(const string&s)
{
bool allSame = true;
for (int i = 1; i < s.size(); i++)
{
if (s[i] != s[i - 1])
{
allSame = false;
string newString(s.begin(), s.begin() + i - 1);
char letter1 = s[i - 1];
char letter2 = s[i];
char otherLetter = 'c';
if (letter1 > letter2)
swap(letter1, letter2);
if (letter1 == 'a' && letter2 == 'c')
otherLetter = 'b';
else if (letter1 == 'b' && letter2 == 'c')
{
otherLetter = 'a';
}
assert(otherLetter != letter1 && otherLetter != letter2);
newString += otherLetter;
newString += string(s.begin() + i + 1, s.end());
//cout << "old string:" << s << " new string: " << newString << endl;
assert(newString.size() == s.size() - 1);
bruteForce(newString);
}
}
if (allSame)
cout << s << endl;
}
int main()
{
#if 0
bruteForce("aaaaabbbbb");
return 0;
#endif
int T;
cin >> T;
for (int t = 0; t < T; t++)
{
string s;
cin >> s;
// Reduce the characters of the string to 0 .. numLetters - 1 :
// makes life a little easier :)
for (auto& character : s)
{
character -= 'a';
}
// Initialise.
for (int i = 0; i < maxStringLength; i++)
{
for (int j = 0; j < maxStringLength; j++)
{
for (int letter = 0; letter < numLetters; letter++)
{
minLetterCountInRange[i][j][letter] = -1;
}
}
}
// Compute.
int minimumLength = std::numeric_limits<int>::max();
for (int letter = 0; letter < numLetters; letter++)
{
const int minOfLetter = calcMinLetterCountInRange(s, 0, s.size() - 1, letter);
if (minOfLetter == 0)
continue;
minimumLength = min(minimumLength, minOfLetter);
//cout << "min of letter " << letter << " = " << minOfLetter << endl;
}
cout << minimumLength << endl;
}
}
String Reduction C Sharp Solution
/*
Enter your code here. Read input from STDIN. Print output to STDOUT
Your class should be named Solution
*/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace string_red
{
class Solution
{
static void Main(string[] args)
{
int tot = Convert.ToInt32(Console.ReadLine());
for (int i = 0; i < tot; i++)
{
Console.WriteLine(Reduce2(Console.ReadLine()));
}
}
static int Reduce2(string input)
{
int ret = 1;
int a_count = input.Count(p => p == 'a');
int b_count = input.Count(p => p == 'b');
int c_count = input.Count(p => p == 'c');
// only one char exists
if (a_count == input.Length || b_count == input.Length || c_count == input.Length)
{
return input.Length;
}
// all odd or all odd
if ((a_count % 2 == b_count % 2) && (b_count % 2 == c_count % 2))
return 2;
return ret;
}
}
}String Reduction Java Solution
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();
}
}String Reduction JavaScript Solution
function processData(input) {
var lines = input.split("\n");
for( var i = 1; i <= lines[0]; i++ ) {
var l = lines[i],
a = 0, b = 0, c = 0;
for( var j = 0; j < l.length; j++ ) {
switch(l[j]) {
case "a":
a++;
break;
case "b":
b++;
break;
case "c":
c++;
break;
}
}
var ae = a % 2 === 0,
be = b % 2 === 0,
ce = c % 2 === 0;
if( !(a || b) || !(b || c) || !(a || c ) ) {
console.log( l.length );
} else {
console.log(!(ae || be || ce) || (ae && be && ce) ? 2 : 1);
}
}
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});String Reduction Python Solution
#!/usr/bin/env python
import collections, sys
char_set = 'abc'
if __name__ == '__main__':
T = int(sys.stdin.readline())
for _ in range(T):
chars = sys.stdin.readline().lower().strip()
count = collections.Counter(chars)
# Set up list of count parities
parities = [v % 2 for v in count.values()]
while len(parities) < len(char_set):
parities.append(0)
# Check if the string is irreducible
if len(count.values()) == 1:
print(len(chars))
elif len(set(parities)) == 1:
print(2)
else:
print(1)
