"Sherlock and the Beast" challenge in Java
As Robert pointed out, your code spends a lot of time in getdecentString. A faster way to generate Strings would be to use the StringBuilder class, e.g.:

StringBuilder decentString = new StringBuilder();
...
for ( int j = 1; j &lt;= x; j++ )
{
    decentString.append( "5" );
}
...
return decentString.toString();