HackerRank Coding Question for Placements

June 24, 2019

You have to classify a string as “GOOD”, “BAD” or “MIXED”. A string is composed of lowercase alphabets and ‘?’. A ‘?’ is to be replaced by any of the lowercase alphabets. Now you have to classify the string on the basis of some rules. If there are more than 3 consonants together, the string is considered to be “BAD”. If there are more than 5 vowels together, the also string is considered to be “BAD”. A string is “GOOD” if its not “BAD”. Now when question marks are involved, they can be replaced with consonants or vowels to make new strings. If all the choices lead to “GOOD” strings then the input is considered as “GOOD”, and if all the choices lead to “BAD” strings then the input is “BAD”, else the string is “MIXED?

LOGIC

1. Convert the string in 0’s and 1’s. All consonants will be considered as 1 and vowels as 0.
2. Make 2 D array (this is dynamic programming approach) and start matching.
3. For string matching, one side will be the string (converted with 0’s and 1’s) and another side with vowels and consonants as 0 and 1.

cons & Vow/ String		W	A	Y	T	O	C	R	A	C	K
	0	1	0	1	1	0	1	1	0	1	1
0	0	0	1	0	0	1	0	0	1	0	0
1	0	1	0	1	2	0	1	2	0	1	2

1. Whenever the 0 will be matched with 0, increment previous array element by 1. Similarly when 1 will be matching with 1, increment previous array element by 1.
2.  In case of 3 consecutive consonants, the current array value reaches to 3 or 5 consecutive vowels the string is said to “BAD”.

Now here comes ? marks case

cons & Vow/ String		W	A	Y	T	?	C	R	A	C	K
	0	1	0	1	1	?	1	1	0	1	1
0	0	0	1	0	0	1	0	0	1	0	0
1	0	1	0	1	2	3	4	5	0	1	2

In case of question mark “?” add one to both consonant and vowel array. Also, make a Boolean flag which will be true in case of “?” occurs. If “?” and 3 consecutive consonants or 5 consecutive vowels occurred then the string is said to be “MIXED”, otherwise the string is “GOOD”.

Please see below code for clear understanding, some of the corner test cases are tested which are also commented there, to test uncomment it and run.

Some more test cases are also given at the end of this post.

 

Code – 

Find if string is good, bad or mixed Code

#include "string.h"
#include"iostream"
using namespace std;

//alphabet check
bool alphabetcheck(char alphabet){
        if (alphabet >= 'a' && alphabet <= 'z')
            return true;
        return false;
    }

//vowel check
int vowelcheck(char vowel)
{
        if (vowel == 'a' || vowel == 'e' || vowel == 'i' || vowel == 'o' || vowel == 'u')
            return 0;
        return 1;
}

    
int main(void) {
    //the two sequences
    //string X = "waytocrack";// ----  GOOD
    //string X = "waaaaaaytocrack";//--BAD
    string X = "wayt?arack";  // mixed
    //length of the sequences
    int XLen = X.size();
    int Arr[2][20];
    memset(Arr, 0, sizeof(Arr[0][0]) * 2 * 20);
    int max0 = 0;
    int max1 = 0;
    int index;
    bool mixed_value = false;
    for (size_t i = 0; i < XLen; i++)
    {
        //alphabet check
        if (alphabetcheck(X[i]))
        {
            //vowel check fucntion:
            if ((vowelcheck(X[i])) == 0)
            {
                Arr[0][i+1] = Arr[0][i] + 1;
                if (Arr[0][i + 1] > max0)
                    max0 = Arr[0][i + 1]; //check for max 0
                if ((mixed_value == true) && (max0 >= 5) && (Arr[0][i + 1] >= 5)) 
// Arr[0][i + 1] >= 5 when current value is greater than 5
                {
                    if ((i - index >= 5 || (Arr[1][index] + Arr[0][index + 5] == 7)))
                     mixed_value = false;
                }
            }
            else
            {
                Arr[1][i + 1] = Arr[1][i] + 1;
                if (Arr[1][i + 1] > max1)
                    max1 = Arr[1][i + 1]; //check for max 1
                if (mixed_value == true && max1 >= 3 && Arr[1][i + 1] >= 3 ) 
 // Arr[0][i + 1] >= 5 when current value is greater than 3
                {
                    if ((i - index >= 3 || (Arr[0][index] + Arr[1][index + 3] == 7)) )
                        mixed_value = false;
                }
            }
            if (mixed_value == false && (max0 >= 5 || max1 >= 3)){
//checking the count value GREATER than  or 3
                cout << " BAD " << endl;
                exit(0);
            }
        }
        
        else if (X[i] == '?'){
            //increament both o count and 1 count.
            Arr[0][i + 1] = Arr[0][i] + 1;
            if (Arr[0][i + 1] > max0)
                max0 = Arr[0][i + 1]; //check for max 1
            Arr[1][i + 1] = Arr[1][i] + 1;
            if (Arr[1][i + 1] > max1)
                max1 = Arr[1][i + 1]; //check for max 1
            index = i;
            mixed_value = true;
        }
    }

    
    if (mixed_value & (max0 >= 5 || max1 >= 3))
        cout << " MIXED " << endl;
    else cout << " GOOD " << endl;
    
    return 0;
}

    These are some corner test cases:

a?fafff	BAD
??aa??	MIXED
abc	GOOD
aaa?aaafff	BAD
aaaa?ff?aaa?aaa?fff	BAD
aaaaff?	MIXED
aaaaf?	GOOD
?aaaaffaaf?aaaafff	BAD
?aaaaffaaf?aaaaff	MIXED
vaxaaaa?bbadadada	BAD
aaaa?bb	BAD
vabb?aaaadadada	BAD
vabab?aaaadadada	MIXED

The solution is 3 or more than 3 consecutive consonants and 5 and more than 5 consecutive vowels.
You can check some of the tested test cases at the end of the code.