Find minimum number of deletions to make a string palindrome

Given a string, delete the minimum number of characters from the string to make the string a palindrome. A palindrome is a sequence of characters that reads the same backward as forward.

Hint

This algorithm count number removals to make a string palindrome.

• 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(word):
  l = len(word)
  
  if l <= 1:
    return 0

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

data = "ratcecafr"

print(count(data))

function count(word) {
  const len = word.length;
  
  if (len <= 1) {
    return 0;
  }

  if (word.at(0) === word.at(len - 1)) {
    return count(word.slice(1, len - 1));
  } else {
    return 1 + Math.min(count(word.slice(1)), count(word.slice(0, -1)));
  }
}

const data = "ratcecafr";

console.log(count(data));