Convert given string into a palindrome by decreasing or increasing characters by their ASCII value, in minimum number of operations. Each decrement or increment is considered as one opeartion. Print the number of operations performed.
See original problem statement here
String Palindrome Test Case
Input:
1
abcd
Output:
4
Explanation:
String 'abcd' can be converted into its palindrome if we convert :
'a'->'d' or 'd'->'a' which takes (ASCII(d) - ASCII(a)) steps i.e. 3 steps.
'b'->'c' or 'c'->'b' which takes (ASCII(b) - ASCII(c)) steps i.e. 1 step.
Hence the total number of steps is 4.
How to find number of moves to make palindrome?
1) Palindrome: A palindrome is a string that contains same characters from both ends. For example,
nitin
can be read same from both ends. Element ati
th index from the start and end side both are the same.2) As we know palindromes contains same characters at
i
th index and(len -i)
th index. So we iterate from 0 to middle of the string and compare all the characters if at some index characters are different, the string is not palindrome. If all the characters remain same, the string is palindrome.3) If two characters are not same at
i
th index and(len -i)
th index, we have to make them the same. We can make them same by adding the ASCII value of difference of both the character to the smaller character.4) Finally we add the difference to our counter, the final value of the counter will be answer according to the fundamentals of data structures in c++.
Example: Number of moves to make palindrome
- Let’s assume given string is
abcds
and we check values from both ends one by one, and check their difference, we take positive difference value as ourstep
.- In
1
st iteration, we comparea
from start ands
from end, we can convert eithera
tos
ors
toa
. Their ASCII value difference is18
, so our current step count is18
.- In
2
nd iteration, we compareb
from start andd
from end, we can convert eitherb
tod
ord
tob
. Their ASCII value difference is2
, so our current step count is20
.- As last element left is middle element,which is also a palindrome in it’s own, so we’ll skip that. Hence We get our final count as
20
.
Solution to find minimum number of moves to make palindrome:
#include <stdio.h> int main() { int test; scanf("%d", &test); while(test--){ char a[10000001]; scanf("%s", a); int no_of_operations = 0; for(int i=0; i<strlen(a)/2; i++){ no_of_operations += abs( a[strlen(a)-i-1] - a[i] ); } printf("%d\n", no_of_operations); } }
#include <bits/stdc++.h> using namespace std; int main() { int test; cin>>test; while(test--){ char a[10000001]; cin>>a; int no_of_operations = 0; for(int i=0; i<strlen(a)/2; i++){ no_of_operations += abs( a[strlen(a)-i-1] - a[i] ); } cout<<no_of_operations<<endl; } }
import java.util.*; import java.io.*; import java.lang.Math; public class Main { public static void main(String args[]) throws IOException { Scanner sc= new Scanner(System.in); int test = sc.nextInt(); while(test != 0){ String a = sc.next(); int no_of_operations = 0; for(int i=0; i
for _ in range(int(input())): a = input() no_of_operations = 0 for i in range(len(a)//2): no_of_operations += abs( ord(a[len(a)-i-1]) - ord(a[i]) ) print(no_of_operations)
[forminator_quiz id=”936″]
This article tried to discuss the concept of Strings. Hope this blog helps you understand and solve the problem. To practice more problems on Strings you can check out MYCODE | Competitive Programming.