Write an application that finds the 3 longest unique palindromes in a supplied string. For the 3 longest palindromes, report the palindrome, start index and length, in descending order of length.
The above result can as quite a surprise to, even I was not expecting to to be this fast, I mean 0.000297 milliseconds is impressive. Coding challenge complete!
To test the performance of my solution I used the excellentBenchmarkDotNet. The results are as follows:
So initially the problem doesnt look like that much of an issue, so I thought Id challenge my self to write the highest performance solution possible.
Get the latest posts delivered right to your inbox.
The Visual Studio project for this solution can be found in myGitHubrepository.
There are plenty of naive solutions floating around the internet which solve the problem with (O(n^3)) or (O(n^2)) complexity, examining all substrings, testing each one to see it its a palindrome; I was sure it could be done more efficiently so set about finding a better solution.
Host Process Environment Information: BenchmarkDotNet=v0.10.0 OS=Microsoft Windows NT 6.2.9200.0 Processor=Intel(R) Core(TM) i7-6700K CPU 4.00GHz, ProcessorCount=8 Frequency=3914061 Hz, Resolution=255.4891 ns, Timer=TSC Host Runtime=Clr 4.0.30319.42000, Arch=32-bit RELEASE GC=Concurrent Workstation JitModules=clrjit-v4.6.1586.0 Job Runtime(s): Clr 4.0.30319.42000, Arch=32-bit RELEASE Type=Benchmark Mode=Throughput
This code is based on the fact that a palindrome can be centred on either a letter or a space between a letter (for even length palindromes). For each possible palindrome centre, I expand left and right to see if we have a valid palindrome. The method above returns all unique palindromes in source string.
Given the input string:sqrrqabccbatudefggfedvwhijkllkjihxymnnmzpop, the output should be:
I recently took part in a coding challenge to write code to solve a palindrome problem. This blog post details the challenge, and my solution.