Under construction

Still being built. Things may change

Palindrome Factory

Time limit2sMemory limit128 MB

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

Medium7 of 10

Topics
Dynamic programming, String, Brute force
Solved
No attempts yet

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.

Examples6

  1. Example 1

    Input
    babacvabba
    Expected output
    2

  2. Example 2

    Input
    abba
    Expected output
    0

  3. Example 3

    Input
    dabba
    Expected output
    1

  4. Example 4

    Input
    abc
    Expected output
    1

  5. Example 5

    Input
    acxcba
    Expected output
    1

  6. Example 6

    Input
    abcacbd
    Expected output
    1