All Tracks Algorithms Sorting Quick Sort Problem

K- Palindrome

Arrays and Strings, Easy, Sorting


Moriarty has given Sherlock a string challenge.

Sherlock will be given a string S consisting of only lower case English alphabets.

Sherlock needs to find the minimum number of steps required for converting the given string into a
K- Palindrome string.

Note :- Here we are considering 1 based index.

What is a K- Palindrome string ?
Let's define a function f, such that f(i) is the character at ith index in the given string. Now, ith index is considered to be a palindromic index if f(i) = f(len - i + 1) (where len is the length of the given string S).
So, if the number of the palindromic indices in the given string is exactly k , then the string is considered to be a K-palindrome string.

In each step, you are allowed to either increase the character or decrease the character, i.e. - if the character is 'c', you can convert it into 'b' or 'd' in one step. So, steps required to convert 'c' to 'a' will be 2. Of course, you can't increase 'z' or decrease 'a'. So, steps required to convert 'a' to 'z' will be 25. Sherlock needs to use minimum number of such steps. Find the minimum number of steps required to make the given string K - palindrome.

See Sample test-case for better understanding.

Input format:

First line consists of an integer T, denoting the number of testcases.

Each test case consists of 2 lines. First line has a string S and second line has an integer K.

Output format:

For each string, output the minimum number of steps required for converting the given string into a
K- palindrome string .

If it is not possible to convert the given string into a K-palindrome string then output -1.


1 <= T <= 20

1 <= |S| <= 500000

1 <= K <= |S|


Subtask #1 (30 points) : 1 <= |S| <= 500

Subtask #2 (70 points) : Original Constraints


In first testcase, given string is "deck", we need to convert it into a 2-palindrome string as k is given to be 2. Here, we can convert 'e' to 'd' in first step and we can convert 'c' to 'd' in second step. So, in two steps, the string becomes "dddk", which is a 2-palindrome string (as 2nd and 3rd index are palindromic indices). Hence, answer is 2.

In second testcase, given string is "aaaaaa", which is already a 6-palindrome string and so answer is 0.

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: Bash, 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, Swift-4.1, TypeScript, Visual Basic


Initializing Code Editor...
Your Rating:


View All Notifications