All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Dreamplay and Upside Down
Tag(s):

Algorithms, Dynamic Programming, Easy-Medium, String Algorithms

Problem
Editorial
Analytics

Dreamplay likes the strings that read the same upside down, that is, if we reverse the entire string, the string remains unchanged. in other words, palindrome strings
Bob does not want to upset his friend, and would thus like to make some changes, to the string $$ P $$ he already has, so that the string $$ P $$ is liked by dreamplay. Bob is allowed to make only two kinds of changes.

  1. Add a character at end.
  2. Replace a character.

Moreover, since Dreamplay is waiting for the string, Bob wants to do this in minimum steps.
Can you find minimum number of steps needed to change the string $$ P $$ such that it reads same from both ends.

Input
Only line of input consists of the string $$ P $$

Output
Print a single integer, the minimum number of steps needed.

Constraints

  • String P consists only of lowercase latin letters.
  • $$ 1 \leq length(P) \leq 5000 $$
SAMPLE INPUT
axcaa
SAMPLE OUTPUT
1
Explanation

We can change the char 'x' from string "axcaa" to obtain "aacaa" which satisfies the required property.
Thus 1 step is needed.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

July Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications