I was going through its solution, but I can’t get how they have formed a fibonacci relation. Can some one explain the logic?

Suppose you have string abcuuuu , then suppose you have answer for dp_5 and dp_4 , (0-based indexing )

then for u at the the 6th index you have two options either to let it u , then the no. of ways will be dp_5 , or make uu as w ( u at index 5th and 6th) , then the no. of ways will be dp_4. so dp_6=dp_5+dp_4

Hence dp_i=dp_i-1 + dp_i-2

1 Like