All Tracks Algorithms Dynamic Programming Problem

Almost Pallindrome
Tag(s):

Easy-Medium

Problem
Editorial
Analytics

Rohan calls a string almost pallindrome if it can be separated into two halves such that each half is permutation of one another. But if length of string is odd then you can divide the string into two half, and there will be only one extra character that will be the middle character

For example : "radar" is an almost pallindrome because two halves are "ra" and "ar" are permutations of each other and d is extra character which is in the middle of the string.

Given a string X you have to count total adjacent swaps required to convert that string to almost pallindrome . If it is not possible , simply print -1 as output.

Examples / Hints

ramaaamr : This is almost pallindrome as it can be divided into rama and aamr and amar is permutation of aamr or vice versa. So total swaps required are 0

raonraons : This is not almost pallindrome as it can't be divided into two halves such that they are permutation of each other but if we swap s with 4 characters towards left then it would become raonsraon whcih is an almost pallindrome. So total swaps required are 4

Input
First line contains a string as input

Output
Output total adjacent swaps required to make the string almost pallindrome

Constraints
1≤ |String| ≤ 10^6+5

SAMPLE INPUT
rarad
SAMPLE OUTPUT
2
Explanation

If you swap d with two characters on the left then string formed is "radra" which is almost pallindrome

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

Notifications
View All Notifications