Find if string is good, bad or mixed.

+1 vote
asked in Coding(Hiring) by kumar
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 it's 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.
Add question to:

1 Answer

+3 votes
answered by nitin2604
selected by nitin2604
 
Best answer

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. 

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

Please comment if any change or any problem occur in understanding the logic.

commented by kumar
Your solution is for more than 2 consonents and more than 4 wovels , right? The actual problem described above is different .
commented by nitin2604
Hi my 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.
...