HackerRank String Reduction Problem Solution

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  
5

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

HackerRank String Reduction Problem Solution

Table of Contents

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)