Problem Statement |
| | A string composed of a's and b's is either redundant or non-redundant. A string is redundant if and only if it can be expressed as a shorter string replicated multiple times. For example, the string "ababab" is redundant since it is 3 copies of "ab" concatenated together. The string "ab" is called a root of "ababab". The string "aaaa" has 2 roots: "aa" and "a". A nice result in formal languages states that every redundant string has exactly 1 non-redundant root (it may have many redundant roots).
Only considering strings composed of a's and b's, return the number of redundant strings that have the given length. |
| |
Definition |
| | | Class: | RedundantStrings | | Method: | howMany | | Parameters: | int | | Returns: | int | | Method signature: | int howMany(int length) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | length will be between 1 and 60 inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 0 | | There are no redundant strings of length 1. |
|
|
| 1) | |
| | | Returns: 2 | | Both "aa" and "bb" are redundant. |
|
|
| 2) | |
| | | Returns: 4 | | Here the redundant strings are "aaaa", "bbbb", "abab", and "baba". |
|
|
| 3) | |
| | |
| 4) | |
| | |