FastPrepFastPrep
Problem Brief

Count Good Strings

OA

There is a string of length 2N containing only character A and B. The string is called good string if the following two conditions are satisfied:

  • The number of A and number of B in that string will be same and that is N, means N numbers of A and N numbers of B will be present in that string.
  • The number of A will be always greater than or equal to the number of B in any prefix string of that string.

    • Now you are given N and you need to count the number of good strings of length 2N, the answer may be very large so return the answer in modulo 10000.

    1Example 1

    Input
    N = 3
    Output
    5
    Explanation
    Here are the good strings of length 2N when N=3:
    • "AAABBB" good
    • "AABABB" good
    • "AABBAB" good
    • "ABAABB" good
    • "ABABAB" good
    "BABABA" is not a good string because the number of Bs is greater than the number of As in the prefix "BA". Therefore, the count of good strings is 5.

    Constraints

    Limits and guarantees your solution can rely on.

    o_o
    public int countGoodStrings(int N) {
  // write your code here
}
    Input

    N

    3

    Output

    5

    Sign in to submit your solution.