LCC '18 Contest 4 J5 - Making Palindromes

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Assembly, Awk, Brain****, C, C++, Clang, Clang++, COBOL, Coffee, D, Fortran, Go, Haskell, Java, JS, Lisp, LOLCODE, Lua, Mono C#, Mono F#, NASM, NASM64, OCaml, Pascal, Perl, Processing, Python, Racket, Ruby, Rust, Sed, TCL, Text, Turing

A palindrome is a word that is the same backwards as it is forwards (e.g. tattarrattat). Even though most words aren't palindromes, you can always remove or change letters from the word to make it a palindrome (remember that all words of length 0 or 1 are palindromes). For example, larry is not a palindrome, but removing/changing a few letters yields arra, which is a palindrome.

Your task is to determine the minimum number of characters you need to remove or change to make a word a palindrome.

Input Specification

The first line will a string S (1 \le |S| \le 10^3), the word you must turn into a palindrome. S will contain lowercase alphanumeric characters.

Output Specification

Output the minimum number of characters needed to make a word a palindrome.

Sample Input 1

tattarrattat

Sample Output 1

0

Sample Input 2

larry

Sample Output 2

2

Sample Input 3

11abcdcbaa00

Sample Output 3

3

Explanation for Sample 3

One solution would be to turn the 1s into 0s, and remove the last a, yielding 00abcdcba00.


Comments

There are no comments at the moment.