ASLRDR
InterviewTime limit2sMemory limit512 MB
Reorder a string with adjacent swaps so it becomes a palindrome, reporting the minimum number of swaps or Impossible.
- Level
Medium6 of 10
- Topics
- Greedy, Two pointers, String, Implementation
- Solved
- No attempts yet
Problem
Suppose a factory has an assembly line with N stations. At each station, a worker performs a task on the product that may be the same as the task at the previous or next station. The order of these stations is not important, but they must be ordered so that the product enters the line from one side (Left or Right) and exits from the other side (Right or Left) without moving backward along the line. Write a program to reorder an existing assembly line so that it obeys this rule. You may reorder the line with several "station swaps", but you may only swap two adjacent stations.
Input
The first line of input gives n, the number of assembly lines (test cases).
For each test case, one line of input follows, containing a string of up to 100 letters or digits that are the names of the stations.
Output
The output consists of one line per test case. This line contains the least possible number of swaps, or "Impossible" if the stations cannot be reordered to obey the rule.
For example, suppose three tasks named 2, a, and D are currently ordered in an assembly line as "2a2aD". To obey the rule, they must be reordered to "2aDa2" with 3 swaps, as follows:
- swap "aD" to yield "2a2Da"
- swap "2D" to yield "2aD2a"
- swap "2a" to yield "2aDa2"