5 ms·

That's a quadratic solution. Try solving an inverse problem to get insight - how to know if a sequence is almost a palindrome and what's the "palindromicity" me

• im3w1l 6y ago
  No it's not quadratic: since there is at most one conflict it will be linear.
  • andi999 6y ago
    It depends how you count. Is string reversion an O(1) or O(N) operation with N the string length? I believe is is O(N) and if you loop over it N times thats O(N^2), isnt it?
    • im3w1l 6y ago
      I didn't want to post code, but I guess it's the only way I can see to settle the debate. This should be manifestly linear. def check(s): is_palindrome = lambda s: s == s[::-1] if is_palindrome(s): return True d = [a==b for a, b in zip(s, s[::-1])].index(False) return is_palindrome(s[d+1:len(s)-d]) or is_palindrome(s[d:-d-1]) edit: It must be len(s)-d rather than -d, to handle d=0.
  • Someone 6y ago
    I’m not sure it is quadratic, but the “deleting the left or right character” to me, hint it deviates from linear. I think the solution, logically, is to cut the string in two halves, duplicating the center character for odd-length strings (¿or can you ignore it a bit more?), computing edit distance between the front half and the reversed right half, allowing only deletions, and bailing out as soon as you know the answer is larger than one. In real life, optimize away the “cut into two halves” and “reverse” parts, as they will be expensive.