Minimum insertions to form a palindrome

Given string str, find the minimum number of characters to be inserted to make it a palindrome.

Hint

This algorithm can count number removals to make a string palindrome instead.

• If the first and last characters of the string are the same: The number will be count of substring that excludes the first and last characters.
• If the first and last characters of the string are different: The number will be 1 plus minimum between count of subsequences of substring that excludes the first character, and count of subsequences of substring that excludes the last character.

If the string is empty, it has zero palindromic subsequences (return 0).

• Python
• Javascript
•  Run

def count(s):
  if len(s) <= 1:
    return 0

  return  count(s[1:-1]) if s[0] == s[-1] else min(count(s[1:]), count(s[:-1])) + 1

s = 'abcd'

print(count(s))

function count(s) {
  if (s.length <= 1) {
    return 0;
  }

  return (s.at(0) === s.slice(-1)) ? count(s.slice(1, -1)) : Math.min(count(s.slice(1)), count(s.slice(0, -1))) + 1;
}

const str = 'abcd';

console.log(count(str));