Binary Strings Without 3 Consecutive Equal
HardDynamic ProgrammingMathString
Description
Return the number of binary strings of length n that contain no run of three or more equal consecutive characters. Define f(0)=1 (empty string).
Examples
Input:
n = 0Output:
1Explanation:
By convention f(0) equals 1 because there is exactly one length-0 string (the empty sequence).
Input:
n = 3Output:
6Explanation:
All eight length-3 strings except 000 and 111 satisfy the no-three-equal rule, giving 6.
Input:
n = 4Output:
10Explanation:
Of the 16 length-4 binary strings, 10 contain no run of three equal characters.
Constraints
- •
0 ≤ n ≤ 60