Length 1: only one string - "a"
Length 2: "aa", "bb" - 2 strings
Length 3: "aaa", "bba", "abb"
Length (n) = Length (n-1) + Length(n-2),
as we get a string of length $n$, by appending "a" to a string of length $n-1$ as well as by appending "bb" to a string of length $n-2$. (This works only because 'a' and 'bb' doesn't have a common character).
So,
n |
No. of strings |
---|
1 |
1 |
2 |
2 |
3 |
3 |
4 |
5 |
5 |
8 |
6 |
13 |
7 |
21 |
8 |
34 |
9 |
55 |
10 |
89 |
We get no. of strings = 89 (10th Fibonacci number)