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, , 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 of length .
Output format
Print a single integer, the minimum number of actions required.
Sample
Input
madam
Output
0
Input
radecar
Output
1
Explanation
Sample : is already a palindrome, so action is needed.
Sample : 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.
- Starting at the first character moving to the right
- Starting at the last character moving to the left At each step
- If the characters match, nothing needs to be done.
- 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 .
Get hands-on with 1200+ tech skills courses.