Creating a binary string with K pairs

Question

I'm doing the AB problem on TopCoder and my code passes all the system test cases except for one. This is the problem statement:

You are given two ints: N and K. Lun the dog is interested in strings that satisfy the following conditions:

• The string has exactly N characters, each of which is either 'A' or 'B'.
• The string s has exactly K pairs (i, j) (0 <= i < j <= N-1) such that s[i] = 'A' and s[j] = 'B'.

If there exists a string that satisfies the conditions, find and return any such string. Otherwise, return an empty string

My algorithm was to start with a string of length N consisting of all As. Initially the number of pairs is 0. While traversing the string if the number of pairs is less than K I replace the rightmost As with Bs starting from the end of the string. If the number of pairs become greater than K then I replace the As at the beginning of the string with Bs. The number of pairs at any given time is countOfAs * countOfBs.

string createString(int n, int k) {
  string result(n, 'A'); // "AAAA....A"
  int i = 0, j = n - 1; // indexes to modify the string
  int numPairs = 0; // number of pairs
  int countA = n; // count of As in the string
  int countB = 0; // count of Bs in the string
  do {
    if (numPairs > k) {
      result[i++] = 'B';
    }
    else if (numPairs < k) {
      result[j--] = 'B';
      countB++;
    }
    else {
      return result;
    }
    countA--;
    numPairs = countA * countB;
  } while (numPairs != 0); // numPairs will eventually go to 0 as more Bs are added
  return "";
}

The test case which fails for me is N=13, K=29. K being a prime number there is no countOfAs * countOfBs that equals K.

The sample answer gave "AAAABBBBBBABA" as an answer (because you can make pairs from the first 4 As, the first 6 Bs, the second to last A, and the last B, i.e 4*6 + 4*1 + 1*1=29)

Answer 1

Here's a recursive method which creates a solution with the least number of B's:

Start with a string of all A's, and find the rightmost position for which placing a B will create at most K pairs; e.g.:

N=13, K=29  

0123456789ABC  
aaaaaaaaaaaab  <-  position 12 creates 12 pairs  

Then recurse with N = position, K = K - position + #B = 18 and #B = 1, where #B is the number of B's added so far. In the following steps, adding a B in position X will add X pairs, but also decrease the number of pairs created by the already added B's by #B; that's why we increase the required pairs K by #B at each step.

N=12, K=18, #B=1  

0123456789AB  
aaaaaaaaaaab  <-  position 11 adds 11 pairs  

Then recurse with N = 11, K = K - 11 + #B = 9, #B = 2:

N=11, K=9, #B=2  

0123456789A  
aaaaaaaaaba  <-  position 9 creates 9 pairs  

We've reached the exact number of required pairs, so we can stop the recursion, and the complete solution is:

aaaaaaaaababb

As you see there are only two cases at every recursion level: either K ≥ N and a B is added to the end before recursing, or K < N and a B is put at postion K and this completes the solution.

If you add N/2 B's and the value of K is still greater than zero, then there is no valid solution; but you can check this upfront by checking whether (N / 2)² is less than K.

function ABstring(N, K, B) {
    if (B == undefined) {                     // top-level recursion
        if ((N / 2) * (N / 2) < K) return ""; // return if impossible
        B = 0;
    }
    if (K >= N) return ABstring(N - 1, K - (N - 1) + B + 1, B + 1) + 'B';
    var str = "";
    for (var i = 0; i < N; i++) str += (K && i == K) ? 'B' : 'A';
    return str;
}
document.write(ABstring(13, 29));

I initally described the solution created by this method as the lexicographically smallest, but that is not really correct. It creates a solution with the least number of B's, and places each one in its right-most position, but a solution like this:

aaaabaaaabbbb  

can of course be made lexicographically smaller by moving the first B to the right and compensating by moving the second B to the left:

aaaabaaaabbbb  
aaaaabaababbb  
aaaaaabbaabbb  

This transformation could of course be easily incorporated into the algorithm.

Answer 2

You can remark that it is possible to form a string for any value of K in [0, N-1] by building the following string:

B B B ... A B ... B
          ^
          index: N-1-K

You can extend this principle to the following values of K by using two A:

A B B ... A B ... B
          ^
          index: (N-1)-(K-(N-2)) = 2N-3-K

This scheme can produce all values of K in [N, 2N-4].

If you use p As you can produce all values of K in [(p-1)*(N-p), p*(N-p)] by having (p-1) As on the left and one A moving from the right to the left.

For instance, if N=19 and K=23, you can use the string:

A B B ... A B B B B B B
          ^
          index: 2N-3-K = 38-3-23 = 12