Solved Problem - Make String Palindrome

In this lesson, we'll discuss a problem to better understand palindromes.

We'll cover the following

Problem statement

Given a string, SS, of length $$ consisting of lowercase characters, in one action, you have to change any character to any other character.

Find the minimum number of actions required so that the resulting string is a palindrome.

Input format

The single line of input contains the string SS of length N(1N106)N(1 \leq N \leq 10^6).

Output format

Print a single integer, the minimum number of actions required.


Sample

Input

madam

Output

0

Input

radecar

Output

1

Explanation

Sample 11: is already a palindrome, so 00 action is needed.

Sample 22: We can change d to c to get racecar using 1 action.


Solution

For a palindrome, the first character is the same as the last character. Similarly, the second character is the same as the second to last character.

We can iterate using two pointers.

  1. Starting at the first character moving to the right
  2. Starting at the last character moving to the left At each step
  3. If the characters match, nothing needs to be done.
  4. If the characters don’t match, we can make the characters the same using one action.

Since we are iterating over the string once, the time complexity is O(N)O(N).

Get hands-on with 1200+ tech skills courses.