Busy Typing

Problem Statement

Busy Typing Problem Description Mike is a programmer. When he is coding he tries to type the code as fast as possible. Sometimes he tries to write 2 consecutive letters of a string at the same instance of time, but that can cause problems. For example, if the word is "range" and he tries to write the 'g' and the 'e' at the same time instance, then two words can be produced: "range" and "raneg" - that is, the positions of two consecutive letters can be swapped if the two letters are typed at the same instance. He wants to type a given string S of lowercase English letters of length N. If Mike types the i-th and the (i+1)-th character at the same instance, then he cannot type the (i+1)-th and the (i+2)-th character at the same instance, for every valid i. It is not always necessary that he types 2 characters at a time; he can type 1 character at a time too. 1-based indexing is used. Task: Determine how many different strings can be produced because of his busy typing. As this number can