Palindrome With Errors - Part 1
Checking whether a string is a palindrome should be a straightforward question for any programmer. As a matter of fact, this is one of the most boring interview questions on par with the infamous "reverse a linked list".
A more interesting question is the following: given a number N and a string STR, is there a way to remove up to N characters in STR in such a way to make the resulting string a palindrome? As an example, suppose that the string given is "emordnpalindrome" and N=3. Notice that if we remove the 3 characters highlighted below, we end up with a valid palindrome:
Moreover, if there is a way to do so, can you also output the minimum number of changes as well as which characters to change? That seems a more interesting problem, especially given the constraints:
Careful with the execution time here!!! Remember that if you want to select 13 characters randomly out of 120,000 characters, you'll end up with a combination of "120,000 choose 13", which is this pearl: 171709206398765024306410007123271285494715990949929240000. And, remember that, for each one you'd also have to check whether the resulting string is a palindrome (that's linear), hence the brute-force approach would be of the time-order of:
171709206398765024306410007123271285494715990949929240000 * 120000 = this.
There is a better approach. Solution in the next post!!!
Marcelo
A more interesting question is the following: given a number N and a string STR, is there a way to remove up to N characters in STR in such a way to make the resulting string a palindrome? As an example, suppose that the string given is "emordnpalindrome" and N=3. Notice that if we remove the 3 characters highlighted below, we end up with a valid palindrome:
Moreover, if there is a way to do so, can you also output the minimum number of changes as well as which characters to change? That seems a more interesting problem, especially given the constraints:
- 0 <= N <= 13
- 0 <= Len(STR) <= 120,000
Careful with the execution time here!!! Remember that if you want to select 13 characters randomly out of 120,000 characters, you'll end up with a combination of "120,000 choose 13", which is this pearl: 171709206398765024306410007123271285494715990949929240000. And, remember that, for each one you'd also have to check whether the resulting string is a palindrome (that's linear), hence the brute-force approach would be of the time-order of:
171709206398765024306410007123271285494715990949929240000 * 120000 = this.
There is a better approach. Solution in the next post!!!
Marcelo
Comments
Post a Comment