Rearrange Without Adjacent Equals
PHP
Hard
5 views
Problem Description
Rearrange the string so that no two adjacent characters are the same. If not possible, print IMPOSSIBLE.
Input Format
One line string s (lowercase letters).
Output Format
Rearranged string or IMPOSSIBLE.
Official Solution
<?php
$inputText=rtrim(stream_get_contents(STDIN));
if($inputText==='') exit;
$freq=[];
for($i=0,$n=strlen($inputText);$i<$n;$i++){
$ch=$inputText[$i];
if(!isset($freq[$ch])) $freq[$ch]=0;
$freq[$ch]++;
}
$max=0;
foreach($freq as $c) if($c>$max) $max=$c;
if($max > intdiv(strlen($inputText)+1,2)) { echo 'IMPOSSIBLE'; exit; }
function pickChar($freq,$exclude){
$best=null; $bestCnt=-1;
foreach($freq as $ch=>$cnt){
if($cnt<=0) continue;
if($exclude!==null && $ch===$exclude) continue;
if($cnt>$bestCnt){ $bestCnt=$cnt; $best=$ch; }
}
return $best;
}
$out='';
$prev=null;
for($pos=0,$n=strlen($inputText);$pos<$n;$pos++){
$ch=pickChar($freq,$prev);
if($ch===null){ echo 'IMPOSSIBLE'; exit; }
$out.=$ch;
$freq[$ch]--;
$prev=$ch;
}
echo $out;
?>
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!