<?php
$input = 'abca
aaa';

$lines = explode("\n", $input);

foreach ($lines as $line)
{
	$words  = findAnagrams($line);
	$num_words = sizeof($words);
	for ($i = 0; $i < $num_words; ++$i)
	{
		if ($words[$i] <= $line)
		{
			unset($words[$i]);
		}
	}
	if (sizeof($words))
	{
		var_dump(array_shift($words));
	}
	else
	{
		var_dump('no word');
	}
}

function findAnagrams($word)
{
	$sorted = str_split($word);
	sort($sorted);
	return findAnagramsRecursive(implode($sorted));
}

function findAnagramsRecursive($word)
{
	$len = strlen($word);
	if ($len == 0)
	{
		return array();
	}
	if ($len == 1)
	{
		return array($word);
	}

	// For each character in the word, we extract it and find all anagrams
	// where it's the first character.
	$anagrams = array();
	for ($pos = 0; $pos < $len; ++$pos)
	{
		$extractedChar = substr($word, $pos, 1);
		// If same as previous, don't process any further as it will only
		// create duplicates (this is the only check against duplicates,
		// since the word is sorted).
		$sameAsPreviousChar = ($pos > 0 && $extractedChar == substr($word, $pos - 1, 1));

		if (!$sameAsPreviousChar)
		{
			$remaining = substr($word, 0, $pos) . substr($word, $pos + 1);
			$anagramsOfRemaining = findAnagramsRecursive($remaining);
			foreach ($anagramsOfRemaining as $anagramOfRemaining)
			{
				array_push($anagrams, $extractedChar . $anagramOfRemaining);
			}
		}
	}
	return $anagrams;
}

?>