You are not logged in. Please login at www.codechef.com to post your questions!

×

PERMPAL - Editorial

PROBLEM LINK:

Practice
Contest

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[i]=s[p[i]]$, 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\ne 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[i]=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\ne 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.

image 1

  • 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[i]=c$,
    1. 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$;
    2. 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$.
    3. The picture below shows how we fill $p$ when $s=$abdacbabdccba, $i=$b.

image 2

  • 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.

This question is marked "community wiki".

asked 30 Jan, 19:23

r_64's gravatar image

7★r_64
261822
accept rate: 16%

edited 12 Feb, 15:15

admin's gravatar image

0★admin ♦♦
19.1k348495533


Here is my solution https://www.codechef.com/viewsolution/17423799. please help me finding my mistake i am unable to find it.

link

answered 12 Feb, 15:31

tony7's gravatar image

3★tony7
412
accept rate: 0%

edited 12 Feb, 15:38

You are not outputting a correct permutation. The string generated by your permutation is not a palindrome.

Check your solution on the following test cases.

10
ggxggvvxpp
szzsbbhkhk
sjkxkjxsoo
oppdooopoo
ialilpijpp
efefxecxe
ppxuouxpp
vyuvvvyuh
ggwgzzzeg
ggywwwgwg
(12 Feb, 16:11) admin ♦♦0★

thank you so much. found the mistake :)

(12 Feb, 18:01) tony73★

Can someone please help me in finding the problem in my code. Here is the link https://www.codechef.com/viewsolution/17394429
Thanks in advance.

link

answered 13 Feb, 23:12

ayushrusau11's gravatar image

1★ayushrusau11
11
accept rate: 0%

https://www.codechef.com/viewsolution/17340080 Can anyone tell me what was wrong with my solution??

link

answered 15 Feb, 03:46

veda_19's gravatar image

2★veda_19
11
accept rate: 0%

This is my solution https://www.codechef.com/viewsolution/17360282. It works only for subtask #1. can anyone please tell me what went wrong with my solution?

link

answered 26 Feb, 14:02

gauthamnambi's gravatar image

1★gauthamnambi
11
accept rate: 0%

edited 26 Feb, 14:04

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×14,738
×1,034
×560
×232
×192
×151

question asked: 30 Jan, 19:23

question was seen: 1,648 times

last updated: 26 Feb, 14:04