palindrome_index.py

# source: https://www.hackerrank.com/challenges/palindrome-index/problem
# video: https://youtu.be/IoiYMKmvuPQ
    
def is_palindrome(s):
    left = 0
    right = len(s) - 1
    while left < right: # O(n)
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

def palindromeIndex(s):
    # Check from both ends for palindrome, allowing for 1 error
    left = 0
    right = len(s) - 1
    while left < right: # O(n)
        if s[left] != s[right]:
            # Found error!
            # We just don't know which side has the error, so just check both
            if is_palindrome(s[left+1:right+1]):
                return left
            elif is_palindrome(s[left:right]):
                return right
            return -1 # There was more than one error
        left += 1
        right -= 1
    # Total Time Complexity = O(n)
    return -1 # Result was a palindrome without error