CareerCup

In case the input includes number of distinct vowels:

uint64_t Count(int16_t n, int16_t k, int vowels_count, unordered_map<uint64_t, uint64_t> &memo, int prev_vowel = -1) {
	if (k < 0 ||
		n < 0)
	{
		return 0;
	}
	if (k == 0 &&
	    n == 0)
	{
		return 1;
	}

	uint64_t memo_key = ((uint64_t)n << 48) | ((uint64_t)k << 32) | prev_vowel;
	auto it = memo.find(memo_key);
	if (it != memo.end()) {
		return it->second;
	}

	uint64_t count = Count(n - 1, k, vowels_count, memo, -1);
	for (int vowel = 0; vowel < vowels_count; ++vowel) {
		count += Count(n - 1, prev_vowel == vowel ? k - 1 : k, vowels_count, memo, vowel);
	}

	memo[memo_key] = count;
	return memo[memo_key];
}

Consider first a complete search approach, generate all strings of length N with chars from A-Z, then for each of them, compute it's foo value in O(N) time and compare against K. Since there are 26^N such strings, time complexity of complete search is O(N 26^N) which is pretty slow.

Can we do better?

Note that consonants are not considered for the foo value of a string, so represent any of them by using the star symbol *. Generate all strings of length N where chars can be a vowel or a star *, then for each of them, compute it's foo value in O(N), if it equals K, then count the stars in the string and add 21^starsCount to the solution. Given that there are 6^N such strings time complexity is reduced to O(N 6^N), great!

Can we do better?

We can remove the N factor as follows, keep track of 'foo' and 'stars' as we build the strings, foo = 0 and stars = 0 at the beginning. If at step i, 0 <= i < N, pass stars + 1 to the recursive call if extending the current string with a *, or if i > 0 and last char is a vowel and extending the string with that same char for the next step, pass foo + 1 to the recursive call. Doing this reduces the need to run thru the string when we reach step N, so time complexity goes down to O(6^N).

Also knowing that value of foo as we build the solution enables us to backtrack. If at some point foo = K, we can avoid extending with a char that would increase foo. Also if we are at step i, there are N - i remaining steps, if foo = F and K - F > N - i, we can tell it's not possible to make foo = K by extending current path and return early.

Can we do better?

We can see that in the recursion, what determines what the solution following that path will be are: the last selected char (6 possible values), the step number i (N + 1 possible values), and the running value of foo (K + 1 possible values) and starts (N + 1 possible values). It's easy to see that there are 6 * (N + 1) * (K + 1) * (N + 1) different possible states we can be in while doing the recursion, that's O(K N^2). By using dynamic programming to memoize answer for the states we already know the solution for, complexity becomes O(K N^2) for both time and extra space.

But when K=0, you could still have N strings which do not have any consecutive vowels. Returning 1 is not correct for this case. This stumped me in my interview.
What does n<<48 and k<<32 do?

@anonymous. That's right. Thank you! Fixed. It's "k == 0 && n == 0" instead of just "k == 0".

Regarding "n<<48 and k<<32". It's constructing the memo key so, that the values of n and k don't overlap.

@Alex how would you call this?
also this
uint64_t count = prev_is_vowel
? Count(n - 1, k - 1, memo, true)
: Count(n - 1, k, memo, true);

should it not be
uint64_t count = prev_is_vowel
? Count(n - 1, k - 1, memo, true)
: Count(n - 1, k, memo, false);

Count(..., true) is the branch when we use a vowel.
Count(..., false) is the branch when we don't use a vowel.
In the first case, depending on if the previous was a vowel, we decrement k or we don't.
I refactored it into this (though, functionally it's the same thing):

uint64_t count =
Count(n - 1, prev_is_vowel ? k - 1 : k, memo, true) +
Count(n - 1, k, memo, false);

@Alex: for n = 3, k = 2: "AAA", "EEE", "III", "OOO", "UUU" = 5
I don't see how your code comes to this result (if it does, I read out, it returns 1). What did I miss?

@ChrisK. The input is only n and k. We don't have particular vowels. For n = 3, and k = 2, it's only one combination having foo == 2: 'VowelVowelVowel'.

@Alex: The question was: "Set of letters (‘A’, ‘E’, ‘I’, ‘O’, ‘U’) are called vowels. Other letters are called consonants." ...

@ChrisK. I got it like an introduction, to explain how foo is calculated. Then, there goes "You are given 2 inputs, N and K". It may be the case I got it wrong. I've just posted the variant for the case when we know how many vowels we have.

@Alex, sure, you get N and K with the previously explained rules I would suppose. so vowel_count = 5 (constant)

@ChrisK. You are probably right. I removed the first version, and left number of vowels variable to be compatible with different languages :)
O(n * k * v^2) time, O(n * k * v) space. Where v is number of vowels.

go over all the 26^n strings and count

f(n,k,is_previous_vowel)= {if yes then 21*f(n-1,k,false)+4*f(n-1,k,true)+1*f(n-1,k-1,true), if no then 25*f(n-1,k,false)+f(n-1,k,true)}

Recursive approach -

public static void main(String[] args) {
		int N = 5;
		int K = 2;
		System.out.println(count(N, K, K, 1, 1, 0));
	}

	// N=5, K= 2
	public static int count(int N, int K, int k, int p, int count, int total) {

		for (int i = p; i <= N; i++) {
			if(K > 0 && i + 1 <= N) {
				total = count(N, K - 1, k, i + 2, count*5, total);
			}
			if (i <= N) {
				count *= 26;
			}
		}
		if (K == 0){
			total += count;
		}
		return total;
	}

A simple DP solution

int num_c1(int N1, int M1, int t1)
{
	if (N1 == 0)
		return 0;
	if (N1 == 1 && M1 == 0)
	if (t1 == 0)
		return 21;
	else
		return 5;

	if (t1 == 0)
		return num_c1(N1 - 1, M1, 0) * 21 + num_c1(N1 - 1, M1, 1) * 25;
	if (t1 == 1)
		return num_c1(N1 - 1, M1 - 1, 1) + num_c1(N1 - 1, M1, 0) * 5;
	if (t1 == 2)
		return num_c1(N1 - 1, M1, 0) * 21 + num_c1(N1 - 1, M1, 1) * 25 + num_c1(N1 - 1, M1 - 1, 1) + num_c1(N1 - 1, M1, 0) * 5;
}
int main()
{
	cout << num_c1(1, 1, 2) << endl;
	cout << num_c1(3, 1, 2) << endl;
	cout << num_c1(3, 2, 2) << endl;
	cout << num_c1(4, 2, 2) << endl;
	cout << num_c1(4, 3, 2) << endl;
	return 0;
}

Here is a slightly improved version without cutoffs hopefully

// vowel set.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
#include <stdint.h>

bool is_vowel(char c)
{
	return c == 'A' ||
		c == 'E' ||
		c == 'I' ||
		c == 'O' ||
		c == 'U' ||
		c == 'a' ||
		c == 'e' ||
		c == 'i' ||
		c == 'o' ||
		c == 'u';
}


int count(char *s)
{
	int c = 0;

	int state = 0;
	int i = 0;
	while(s[i] != 0)
	{
		switch (state)
		{
		case 0: // last letter was con 
			if (is_vowel(s[i]))
			{
				state = 1;
			}
			break;
		case 1: // last was vowle 
			if (is_vowel(s[i]))
			{
				if (s[i - 1] == s[i])
				{
					c++;
					state = 2;
				}
			}
			else
			{
				state = 0;
			}
			break;
		case 2: // in a sequence 
			if (is_vowel(s[i]))
			{
				if (s[i - 1] != s[i])
				{
					state = 1;
				}
			}
			else
			{
				state = 0;
			}
			break;
		}
		i++;
	}

	return c;
} //----------------------------------------------------------------------------------------------------------------

int test_all_string_r(int n, int k, char *s, int l)
{
	if (l == n)
	{
		//cout << s;

		int x = count(s);
		if (x == k)
		{
			//cout << " *\n";
			return 1;
		}
		else
		{
			//cout << "\n";
			return 0;
		}
	}
	
	int sum = 0;

	for (char c = 'A'; c <= 'Z'; c++)
	{
		s[l] = c;
		sum = sum + test_all_string_r(n, k, s, l + 1);
	}

	return sum;
}//----------------------------------------------------------------------------------------------------------------

int test_all_string(int n, int k)
{
	char *s = new char[n + 1];
	s[n] = 0;

	int out = test_all_string_r(n, k, s, 0);

	delete[] s;
	return out;
}//----------------------------------------------------------------------------------------------------------------

void dump(const vector<vector<uint64_t>> &in)
{
	for (int y = 0; y < in[0].size(); y++)
	{
		for (int x = 0; x < in.size(); x++)
		{
			cout << in[x][y] << " ";
		}
		cout << "\n";
	}
}

uint64_t dp_cont_2(int n, int k) // n > 1 and k > 0
{
	vector<vector<uint64_t>> end_consonant(n + 1, vector<uint64_t>(k + 1, 0));
	vector<vector<uint64_t>> end_vowel_set(n + 1, vector<uint64_t>(k + 1, 0));
	vector<vector<uint64_t>> end_single_vowel(n + 1, vector<uint64_t>(k + 1, 0));
	vector<vector<uint64_t>> total(n + 1, vector<uint64_t>(k + 1, 0));

	end_consonant[1][0] = 26 - 5; // any of the consonants
	end_single_vowel[1][0] = 5; // any of the vowels
	total[1][0] = 26;

	for (int ni = 2; ni <= n; ni++) 
	{
		for (int ki = 0; ki <= k; ki++)
		{
			end_consonant[ni][ki] = total[ni - 1][ki] * (26 - 5); 
			// ways of doing it with one less letter and then we add a new consonant at the end 

			uint64_t ec = end_consonant[ni][ki];

			end_single_vowel[ni][ki] = end_single_vowel[ni - 1][ki] * 4 + // add a different vowel 
				end_vowel_set[ni - 1][ki] * 4 + // add a different vowel
				end_consonant[ni - 1][ki] * 5; // add any vowel 

			uint64_t esv = end_single_vowel[ni][ki];

			if (ki > 0)
			{
				uint64_t d = end_single_vowel[ni - 1][ki - 1];
				end_vowel_set[ni][ki] = end_vowel_set[ni - 1][ki] + d;
			}
			else
			{
				end_vowel_set[ni][ki] = end_vowel_set[ni - 1][ki];
			}


			uint64_t evs = end_vowel_set[ni][ki];

			total[ni][ki] = end_consonant[ni][ki] + 
				end_vowel_set[ni][ki] + 
				end_single_vowel[ni][ki]; // total ways with one less letter 

			uint64_t t = total[ni][ki];

		}
	}

	cout << "--------end_consonant---------------------------------------\n";
	dump(end_consonant);
	cout << "--------end_vowel_set---------------------------------------\n";
	dump(end_vowel_set);
	cout << "--------end_single_vowel---------------------------------------\n";
	dump(end_single_vowel);
	cout << "--------total---------------------------------------\n";
	dump(total);
	cout << "-----------------------------------------------\n";

	return total[n][k];
}




int _tmain(int argc, _TCHAR* argv[])
{
	cout << "(1, 0) " << test_all_string(1, 0) << '\n';
	cout << "(1, 1) " << test_all_string(1, 1) << '\n';
	cout << "(2, 0) " << test_all_string(2, 0) << '\n';
	cout << "(2, 1) " << test_all_string(2, 1) << '\n';
	cout << "(3, 1) " << test_all_string(3, 1) << '\n';
	cout << "(4, 2) " << test_all_string(4, 2) << '\n';
	cout << "(5, 2) " << test_all_string(5, 2) << '\n';

	cout << dp_cont_2(5, 2);


	return 0;
}

Python simple solution

def cons_vowel(s):
  vowel = ['A','E','I','O','U']
  counter = 0
  for i in range(len(s)-1):
    if s[i] in vowel:
      if s[i] == s[i+1]:
        counter += 1
  
  return counter

public class FooCount {

public static void main(String[] args) {
// TODO Auto-generated method stub
int strLength = 5;
int foolength = 3;
int value =0;

for(int i=1; i<=strLength; i++) {
if(i>=foolength) {
int CombCount = strLength-(i-1);
value = value + (i-(foolength-1))*CombCount;
}
}

System.out.println("the favoriye combinations:"+ value);

}

}

"public class FooCount {

public static void main(String[] args) {
// TODO Auto-generated method stub
int strLength = 5;
int foolength = 3;
int value =0;

for(int i=1; i<=strLength; i++) {
if(i>=foolength) {
int CombCount = strLength-(i-1);
value = value + (i-(foolength-1))*CombCount;
}
}

System.out.println("the favoriye combinations:"+ value);

}

}"

public class FooCount {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int strLength = 5;
		int foolength = 3;
		int value =0;
		
		for(int i=1; i<=strLength; i++) {
			if(i>=foolength) {
				int CombCount =  strLength-(i-1);
				value = value + (i-(foolength-1))*CombCount;
			}
		}
		
		System.out.println("the favoriye combinations:"+ value);

	}

}

public class FooCount {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int strLength = 5;
		int foolength = 3;
		int value =0;
		
		for(int i=1; i<=strLength; i++) {
			if(i>=foolength) {
				int CombCount =  strLength-(i-1);
				value = value + (i-(foolength-1))*CombCount;
			}
		}
		
		System.out.println("the favoriye combinations:"+ value);

	}

}

int strLength = 5;
		int foolength = 3;
		int value =0;
		
		for(int i=1; i<=strLength; i++) {
			if(i>=foolength) {
				int CombCount =  strLength-(i-1);
				value = value + (i-(foolength-1))*CombCount;
			}
		}
		
		System.out.println("the favoriye combinations:"+ value);

"
int strLength = 5;
		int foolength = 3;
		int value =0;
		
		for(int i=1; i<=strLength; i++) {
			if(i>=foolength) {
				int CombCount =  strLength-(i-1);
				value = value + (i-(foolength-1))*CombCount;
			}
		}
		
		System.out.println("the favoriye combinations:"+ value);
"

Here is a dp solution and a brute force solution. You can improve the DP solution by removing the total array and reducing the other matrices to a pair of vectors that you swap on every cycle.

#include <iostream>
#include <vector>
using namespace std;
#include <stdint.h>

int count(char *s)
{
	int c = 0;

	int state = 0;
	int i = 0;
	while(s[i] != 0)
	{
		switch (state)
		{
		case 0: // last letter was con 
			if (s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U')
			{
				state = 1;
			}
			break;
		case 1: // last was vowle 
			if (s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U')
			{
				if (s[i - 1] == s[i])
				{
					c++;
					state = 2;
				}
			}
			else
			{
				state = 0;
			}
			break;
		case 2: // in a sequence 
			if (s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U')
			{
				if (s[i - 1] != s[i])
				{
					state = 1;
				}
			}
			else
			{
				state = 0;
			}
			break;
		}
		i++;
	}

	return c;
} //----------------------------------------------------------------------------------------------------------------

int test_all_string_r(int n, int k, char *s, int l)
{
	if (l == n)
	{
		//cout << s;

		int x = count(s);
		if (x == k)
		{
			//cout << " *\n";
			return 1;
		}
		else
		{
			//cout << "\n";
			return 0;
		}
	}
	
	int sum = 0;

	for (char c = 'A'; c <= 'Z'; c++)
	{
		s[l] = c;
		sum = sum + test_all_string_r(n, k, s, l + 1);
	}

	return sum;
}//----------------------------------------------------------------------------------------------------------------

int test_all_string(int n, int k)
{
	char *s = new char[n + 1];
	s[n] = 0;

	int out = test_all_string_r(n, k, s, 0);

	delete[] s;
	return out;
}//----------------------------------------------------------------------------------------------------------------
void dump(const vector<vector<uint64_t>> &in)
{
	for (int y = 0; y < in[0].size(); y++)
	{
		for (int x = 0; x < in.size(); x++)
		{
			cout << in[x][y] << " ";
		}
		cout << "\n";
	}
}

uint64_t dp_cont_2(int n, int k) // n > 1 and k > 0
{
	vector<vector<uint64_t>> end_consonant(n + 1, vector<uint64_t>(k + 1, 0));
	vector<vector<uint64_t>> end_vowel_set(n + 1, vector<uint64_t>(k + 1, 0));
	vector<vector<uint64_t>> end_single_vowel(n + 1, vector<uint64_t>(k + 1, 0));
	vector<vector<uint64_t>> total(n + 1, vector<uint64_t>(k + 1, 0));

	end_consonant[1][0] = 26 - 5; // any of the consonants
	end_single_vowel[1][0] = 5; // any of the vowels
	total[1][0] = 26;

	for (int ni = 2; ni <= n; ni++) 
	{
		for (int ki = 0; ki <= k; ki++)
		{
			end_consonant[ni][ki] = total[ni - 1][ki] * (26 - 5); // ways of doing it with one less letter and then we add a new consonant at the end 

			uint64_t ec = end_consonant[ni][ki];

			end_single_vowel[ni][ki] = end_single_vowel[ni - 1][ki] * 4 + // add a different vowel 
				end_vowel_set[ni - 1][ki] * 4 + // add a different vowel
				end_consonant[ni - 1][ki] * 5; // add any vowel 

			uint64_t esv = end_single_vowel[ni][ki];

			if (ki > 0)
			{
				uint64_t d = end_single_vowel[ni - 1][ki - 1];
				end_vowel_set[ni][ki] = end_vowel_set[ni - 1][ki] + d;
			}
			else
			{
				end_vowel_set[ni][ki] = end_vowel_set[ni - 1][ki];
			}

			end_vowel_set[ni][ki] = ((ki > 0) ? end_single_vowel[ni - 1][ki - 1] : 0) + // k went up so we need to have i-1
				end_vowel_set[ni - 1][ki]; // add a vowel after eithe a uneque v and a set of vs 

			uint64_t evs = end_vowel_set[ni][ki];

			total[ni][ki] = end_consonant[ni][ki] + end_vowel_set[ni][ki] + end_single_vowel[ni][ki]; // total ways with one less letter 

			uint64_t t = total[ni][ki];

		}
	}

	cout << "--------end_consonant---------------------------------------\n";
	dump(end_consonant);
	cout << "--------end_vowel_set---------------------------------------\n";
	dump(end_vowel_set);
	cout << "--------end_single_vowel---------------------------------------\n";
	dump(end_single_vowel);
	cout << "--------total---------------------------------------\n";
	dump(total);
	cout << "-----------------------------------------------\n";

	return total[n][k];
}




int _tmain(int argc, _TCHAR* argv[])
{
	cout << "(1, 0) " << test_all_string(1, 0) << '\n';
	cout << "(1, 1) " << test_all_string(1, 1) << '\n';
	cout << "(2, 0) " << test_all_string(2, 0) << '\n';
	cout << "(2, 1) " << test_all_string(2, 1) << '\n';
	cout << "(3, 1) " << test_all_string(3, 1) << '\n';
	cout << "(4, 2) " << test_all_string(4, 2) << '\n';
	cout << "(5, 2) " << test_all_string(5, 2) << '\n';

	cout << dp_cont_2(5, 2);


	return 0;
}

Here is a dp solution and a brute force solution. You can improve the DP solution by talking out the total array and reducing the other matrices to a pair of vectors that you swap on every cycle.

#include <iostream>
#include <vector>
using namespace std;
#include <stdint.h>

int count(char *s)
{
	int c = 0;

	int state = 0;
	int i = 0;
	while(s[i] != 0)
	{
		switch (state)
		{
		case 0: // last letter was con 
			if (s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U')
			{
				state = 1;
			}
			break;
		case 1: // last was vowle 
			if (s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U')
			{
				if (s[i - 1] == s[i])
				{
					c++;
					state = 2;
				}
			}
			else
			{
				state = 0;
			}
			break;
		case 2: // in a sequence 
			if (s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U')
			{
				if (s[i - 1] != s[i])
				{
					state = 1;
				}
			}
			else
			{
				state = 0;
			}
			break;
		}
		i++;
	}

	return c;
} //----------------------------------------------------------------------------------------------------------------

int test_all_string_r(int n, int k, char *s, int l)
{
	if (l == n)
	{
		//cout << s;

		int x = count(s);
		if (x == k)
		{
			//cout << " *\n";
			return 1;
		}
		else
		{
			//cout << "\n";
			return 0;
		}
	}
	
	int sum = 0;

	for (char c = 'A'; c <= 'Z'; c++)
	{
		s[l] = c;
		sum = sum + test_all_string_r(n, k, s, l + 1);
	}

	return sum;
}//----------------------------------------------------------------------------------------------------------------

int test_all_string(int n, int k)
{
	char *s = new char[n + 1];
	s[n] = 0;

	int out = test_all_string_r(n, k, s, 0);

	delete[] s;
	return out;
}//----------------------------------------------------------------------------------------------------------------
void dump(const vector<vector<uint64_t>> &in)
{
	for (int y = 0; y < in[0].size(); y++)
	{
		for (int x = 0; x < in.size(); x++)
		{
			cout << in[x][y] << " ";
		}
		cout << "\n";
	}
}

uint64_t dp_cont_2(int n, int k) // n > 1 and k > 0
{
	vector<vector<uint64_t>> end_consonant(n + 1, vector<uint64_t>(k + 1, 0));
	vector<vector<uint64_t>> end_vowel_set(n + 1, vector<uint64_t>(k + 1, 0));
	vector<vector<uint64_t>> end_single_vowel(n + 1, vector<uint64_t>(k + 1, 0));
	vector<vector<uint64_t>> total(n + 1, vector<uint64_t>(k + 1, 0));

	end_consonant[1][0] = 26 - 5; // any of the consonants
	end_single_vowel[1][0] = 5; // any of the vowels
	total[1][0] = 26;

	for (int ni = 2; ni <= n; ni++) 
	{
		for (int ki = 0; ki <= k; ki++)
		{
			end_consonant[ni][ki] = total[ni - 1][ki] * (26 - 5); // ways of doing it with one less letter and then we add a new consonant at the end 

			uint64_t ec = end_consonant[ni][ki];

			end_single_vowel[ni][ki] = end_single_vowel[ni - 1][ki] * 4 + // add a different vowel 
				end_vowel_set[ni - 1][ki] * 4 + // add a different vowel
				end_consonant[ni - 1][ki] * 5; // add any vowel 

			uint64_t esv = end_single_vowel[ni][ki];

			if (ki > 0)
			{
				uint64_t d = end_single_vowel[ni - 1][ki - 1];
				end_vowel_set[ni][ki] = end_vowel_set[ni - 1][ki] + d;
			}
			else
			{
				end_vowel_set[ni][ki] = end_vowel_set[ni - 1][ki];
			}

			end_vowel_set[ni][ki] = ((ki > 0) ? end_single_vowel[ni - 1][ki - 1] : 0) + // k went up so we need to have i-1
				end_vowel_set[ni - 1][ki]; // add a vowel after eithe a uneque v and a set of vs 

			uint64_t evs = end_vowel_set[ni][ki];

			total[ni][ki] = end_consonant[ni][ki] + end_vowel_set[ni][ki] + end_single_vowel[ni][ki]; // total ways with one less letter 

			uint64_t t = total[ni][ki];

		}
	}

	cout << "--------end_consonant---------------------------------------\n";
	dump(end_consonant);
	cout << "--------end_vowel_set---------------------------------------\n";
	dump(end_vowel_set);
	cout << "--------end_single_vowel---------------------------------------\n";
	dump(end_single_vowel);
	cout << "--------total---------------------------------------\n";
	dump(total);
	cout << "-----------------------------------------------\n";

	return total[n][k];
}




int _tmain(int argc, _TCHAR* argv[])
{
	cout << "(1, 0) " << test_all_string(1, 0) << '\n';
	cout << "(1, 1) " << test_all_string(1, 1) << '\n';
	cout << "(2, 0) " << test_all_string(2, 0) << '\n';
	cout << "(2, 1) " << test_all_string(2, 1) << '\n';
	cout << "(3, 1) " << test_all_string(3, 1) << '\n';
	cout << "(4, 2) " << test_all_string(4, 2) << '\n';
	cout << "(5, 2) " << test_all_string(5, 2) << '\n';

	cout << dp_cont_2(5, 2);


	return 0;
}