Microsoft take home qutsion

Microsoft Take Home Question

You are given a string S consisting of N letters. In a single move, you can remove a letter from either the left or the right end of S. A palindrome is a word that reads the same both forwards and backwards. An empty string is not considered to be a palindrome. For example:

"aba", "c" and "xyzzyx" are palindromes; "fg", "abbac" and an empty string (*) are not palindromes. Your task is to find the minimum number of moves required so that the resulting string is not a palindrome.

Write a function:

fun solution(S: String): Int

that, given a string S consisting of N characters, returns the minimum number of moves needed.

Examples:

Given S = "xyzx", the function should return 0 because S is already not a palindrome. Given S = "kayak", the function should return 1. By deleting one letter from the left, you obtain the string "ayak", which is not a palindrome. Given S = "xxxx", the function should return 4. The only option is to delete all the letters one by one from S to obtain an empty string, which is not a palindrome. Given S = "abba", the function should return 1.

Write an efficient algorithm for the following assumptions:

string S is made only of lowercase letters (a-z); N is an integer within the range [1..100,000].