CareerCup

int string=0;
int form_string(int i,char ch,int countA,int countB)
{
if(i==N)
{
string++;
return;
}
else if(countA==N/2&&ch=='A')
{
return;
}
else if(countA==countB&&ch=='B')return;
else
{
if(ch=='A')countA++;elseif(ch=='B')countB++;
form_string( i+1,'A',countA,countB);
form_string(i+1,'B',countA,countB);
}
}
call this fuinction by form_string(0,'A',0,0);

Simple Recursion:

public static void main(String[] args) {

		findCombination(3);
	}

	public static void findCombination(int count) {

		StringBuilder sb = new StringBuilder();
		findCombination(count, count, sb);
	}

	public static void findCombination(int countA, int countB, StringBuilder sb) {

		if (countA == 0 && countB == 0) {
			System.out.println(sb);
			return;
		}

		if (countA > 0) {
			sb.append("A");
			findCombination(countA - 1, countB, sb);
			sb.setLength(sb.length() - 1);
		}
		if (countB > countA) {
			sb.append("B");
			findCombination(countA, countB - 1, sb);
			sb.setLength(sb.length() - 1);
		}
	}

C(2n,n)/(n+1), The catalan number.

use dynamical programming
O(n^2)

please explain the qn . input and output is integer . but then where does the string formation come

Hey,

Can you please word the question more clearly. I apologize for being blunt and am absolutely not pointing at you, but I'm so freaking irritated that so many people here don't write their questions clearly or use awfully constructed sentences with incomplete information and ASSUME the readers already know the question.

I understood the parts about strings and rules of the grammar for possible strings.

Specifically, could you please clear these ambiguities:
1. What do "iln" the input integer and iOp the output integer correspond to? - String length? no. of correct matches?
2. Elaborate on this - "Given iIn, then find the number of possible string which match this criteria iOp"

A possible test case would do no harm.

Thanks :)

Sorry for the very badly framed question. Let me try my best to make the question readable. A string can contain only the characters A and B.

The string formation must follow the following rules
1. The number of occurences of A and that of B must be equal in the string
2. For any prefix of string, the number occurences of A must be greater than or equal to the number of occurences of B.

Now given an integer of length N, find the number of possible string formations adhering the rules above.

Sorry for the very badly framed question. Let me try my best to make the question readable. A string can contain only the characters A and B.

The string formation must follow the following rules
1. The number of occurences of A and that of B must be equal in the string
2. For any prefix of string, the number occurences of A must be greater than or equal to the number of occurences of B.

Now given an integer of length N, find the number of possible string formations adhering the rules above.

@furious_coder.
thanks for the updated ques.

Another insight can help..
N lenght must be even and will have n/2 A and n/2 B

now fix one B at the last end and generate all possible permutatiosn posible..
(Think it is necessary and sufficient tooo..)
this gives the answer.

This can be solved in O(n^3). The question is similar to the question which asks the number of ways in which an expression can be parenthesized.

We maintain a matrix NOP[n,n] where n is the size of the list. Now between ever pair of i & j such that j>i we iterate for all k such that k lies between i & j.

NOP[i,j] = for all k : i<k<j { NOP[i,k] + NOP[k,j]}

This will run in O(n^3). Can anyone better this ?

<pre lang="" line="1" title="CodeMonkey84234" class="run-this">#include<iostream.h>
using namespace std;
void make(string ans,int l,int a,int b){
if(a+b == l){
cout<<ans<<endl;
}
else if(a==b){
make(ans+'a'+'b',l,a+1,b+1);
if(a+b+2 < l)
make(ans+'a'+'a',l,a+2,b);
}
else {
make(ans+'b',l,a,b+1);
}
}
main(){
string ans = "";
int n;
cin>>n;
make(ans,n,0,0);
system("pause");
}
</pre><pre title="CodeMonkey84234" input="yes">4
abab
aabb

</pre>

why are making this thing complex.. its just a mathematical puzzle isn't it??

"Now given an integer of length N". I still dont get the meaning of the question. What do you mean by this statement?

I think, it is about inserting AB in this blank. _AB or A_B. That is inserting AB before or after every A and also at the end with respect to the string of length N-1 and find the number of times distinct strings occur.

DP

www[dot]geeksforgeeks[dot]org / check-whether-a-given-string-is-an-interleaving-of-two-other-given-strings-set-2 /

#include<iostream>
#include<string.h>
using namespace std;

void foo(int n, int l, int r, char ch[], int i)
{
    if(r == n)
    {
        ch[i]='\0';
        cout<<ch<<endl;
        return;
    }
    
    if(l<n)
    {
        ch[i] = 'A';
        foo(n, l+1, r, ch, i+1);
    }

    if(r<l)
    {
        ch[i] = 'B';
        foo(n, l, r+1, ch, i+1);
    }
    return;
}

int main()
{
    int n;
    cin>>n;
    char ch[1000];
    foo(n, 0, 0, ch, 0);

    return 0;
}