CareerCup

(N-2)*2^(N-3)

Well, it seems there is no right and easy solution so far.
I do believe it is possible to think of a nice and easy solution.
How many strings of 'a's and 'b's we can make? It is 2^(N) where N is the length of the string and 2 is a number of different symbols.
How many strings with "bbb" in them? We reduce the length of the string by 3(it is 2^(N-3)) and put "bbb" into all possible position into each such strings. How many positions? N-3+1 = N-2;
So, it is the initial formula from the first answer - (N-2)*2^(N-3). Now we have to handle the duplicates.
When do we have a duplicate? Then we insert "bbb" before "b" symbol in the string - the next insertion will give us the same result. How many times we insert before "b"? Half of the total number of insertion (there is the same number of insertions before "a" and before "b"). So, each insertion before "a" and after "a" give the different unique combinations, and insertion before "b" and after "b" gives the same unique combination. So, all we need to do is to multiply the formula by 3/4.
The resulting formula is (3/4)(N-2)*2^(N-3).
The general version is (3/4)(N-b+1)2^(N-b) where b is the length of "bb..bbb" string.
The code in C/C++

int GetNumberOfString(int N, int b)
{
return (3*N-3*b+3)*(pow(2, N-b))/4;
}

Is this question should not be solved using recursion (like we do in permutations of a string however, with additional conditions) or the interviewer expect only the formula from us?

import java.math.BigInteger;

public class Solution {

	public static void main(String[] args) {
		
		System.out.println(new Solution().count(10)); // = 520
		
		
		/*
		 * N = 500
		 * Result = 3273390607896141870013189696827599152216642046043064789483291368096133796404674554883270092325904157150886684127560071009217256545885393053328843506427
		 */
		System.out.println(new Solution().count(500));
	}

    BigInteger count(int N) {

		if (N < 3)
			return new BigInteger("0");

		int x_1 = 2;
		int x_2 = 4;
		int x_3 = 7;

		for (int i = 4; i <= N; i++) {
			int temp = x_1 + x_2 + x_3;

			x_1 = x_2;
			x_2 = x_3;
			x_3 = temp;
		}

		BigInteger e = new BigInteger("2");
		return (e.pow(N).subtract(new BigInteger(String.valueOf(x_3))));
	}

}

We can apply BFS here. We can start from bbb and then for every iteration we will have four different strings like: bbb+'a', 'a'+bbb, 'b'+bbb, bbb+'b'. As last two strings are same we will only add one in the queue. Now we can keep on iterating until our N becomes 0.

This problem is similar problem like step numbers.

(N-2)*2^(N-3) - 1

(N-2)*2^(N-3) - 1 (for redundant count )

It looks like that solution from the above is not right...
let's assume that n is length of a word and q is number of consequent numbers.
for n = 6 and q = 3 we should consider following cases ('_' is a place where could be rather 'A' or 'B'):
1. BBB___ --> 8 different cases. --> 8 unique cases. --> 2^(n - q)
2. _BBB__ --> 8 different cases, but 4 is similar to case 1. --> 4 unique cases. --> 2^(n - q - 1)
3. __BBB_ --> 8 different cases, but 4 is similar to case 2. --> 4 unique cases. --> 2^(n - q - 1)
4. ___BBB --> 8 different cases, but 4 is similar to case 3. --> 4 unique cases. --> 2^(n - q - 1)

amount of shifts with amount of unique cases that equals to 2^(n - q - 1) is (n - q)

and 20 unique cases in total.

so, it means that total number of cases is 2^(n - q) + (n - q)*2^(n - q - 1) == (n - q + 2)*2^(n - q - 1)

so implementation is the following:

/**
 * Count number of strings of length N with following properties:
 *
 * A. Consists of char 'A' and 'B' only.
 * B. There is at least one occurrence of 3 consecutive Bs.
 */
public class StringWithProperties {

  private final long modulo = 1000000007L;

  long getNumberOfStringsByModuloWithLength(int n, int q) {
    if (n < q) {
      return 0L;
    }

    long expectedNumber = n - q + 2;

    if (n - q - 1 >= 0) {
      for (int i = 0; i < n - q - 1; i++) {
        expectedNumber <<= 1;
        expectedNumber %= modulo;
      }
    } else {
      expectedNumber >>= 1;
      expectedNumber %= modulo;
    }

    return expectedNumber;
  }
}