cho.sh

Palindrome Factory

Compute the minimum number of insertions, deletions, replacements, and at most one swap needed to turn a given string into a palindrome.

Medium7Dynamic programmingStringBrute forceNo attempts yetTime limit2sMemory limit128 MB

Problem

A palindrome is a string that reads the same from left to right and from right to left.

You may use the following operations to turn a string into a palindrome.

  1. Insert any character at any position in the string, including the beginning or the end.
  2. Delete the character at any position.
  3. Replace the character at any position with another character.
  4. Swap the characters at two different positions.

Operations 1, 2, and 3 may be used any number of times. Operation 4 may be used at most once.

Given a string, find the minimum number of operations needed to make it a palindrome.

Input

The first line contains a string. It consists only of lowercase English letters, and its length is at most 50.

Output

Print the minimum number of operations needed.