### PROBLEM LINK:

**Author:** Praveen Dhinwa

**Tester:** Hanlin Ren

**Editorialist:** Hanlin Ren

### DIFFICULTY:

SIMPLE

### PREREQUISITES:

None

### PROBLEM:

Given a string s[1\sim n], does there exist a permutation p of 1,2,\dots,n such that, if we let t*=s[p*], then t is palindrome?

### EXPLANATION:

This problem is equivalent to: can we rearrange the characters of s into a permutation?

Let’s count the number of occurrences of every characters in `a-z`

. For a char c, let cnt[c] be the number of times c occur in s.

If there are two chars c_1,c_2(c_1 e c_2) such that both cnt[c_1] and cnt[c_2] is odd, then the answer is no.

- To see this, consider any palindromic string t and any char c. Suppose t*=c.
- If the length n of t is even, then t[n-i+1]=c. Since n is even, n-i+1 and i has different parity and hence i e n-i+1. Also n-(n-i+1)+1=i, so we say i and n-i+1 is a pair. Any pair must use the same character, so any character must occur an even number of times.
- If the length n of t is odd, the above argument holds, too, except that the central char(t[\frac{n+1}{2}]) is matched with itself. In this case, this char appears an odd number of times, and is the only char that appears an odd number of times.
- See figure below. n=7, pairs are (1,7),(2,6),(3,5), and t[4] is matched with itself, and hence appears an odd number of times.

- In conclusion, if C is the number of chars c that cnt[c] is odd, and s can be arranged into a palindrome, then C\le 1.

The converse is also true: if there are at most 1 characters c with cnt[c] odd, then the answer is yes. Here is **one of** the constructions.

- Let’s construct the permutation char-by-char. Let c iterate from
`a`

to`z`

.- If cnt[c] is odd, we ignore c(that is, we consider c later). At most one such c exists.
- We maintain two pointers l and r. Initially l=0,r=n+1. The permutation p[1\sim l] and p[r\sim n] is already filled.
- We scan s. Each time we meet a c, say t*=c,
- if this is the 1,3,5,\dots,(odd) time we meet c, we assign it to the left: l\gets l+1 and p[l]\gets i;
- otherwise (this is the 2,4,6,\dots time we meet c), we assign it to the right: r\gets r-1 and p[r]\gets i.
- The picture below shows how we fill p when s=
`abdacbabdccba`

, i=`b`

.

- At last, in case that n is odd, we need to deal with the c where cnt[c] is odd. That’s easy: p[l+1\sim r-1] is unfilled, and we fill them by char c.
- This is a valid answer. Time complexity: O(\sigma\cdot n). (\sigma=26)

### ALTERNATIVE SOLUTIONS

This is a constructive problem. I think there’ll be many solutions. **Please feel free to share your solution.**

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.