Hint:⌗

Maintain a function with current position of the string that can we take and number of last character that we have taken as state.

We have three option for transition:

  • take current charecter as the new character of our abcdef... string [if it is possible], and go to the next position of our given string.

  • ignore the current character , and go to the next position of our given string.

  • insert a new character as the new character of our abcdef... string, and stay at the same position of our given string.

Saving all state in DP table is enough for this problem.

Reference:⌗