Showing posts from July, 2015

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: 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&#