Minimum Insertions for Palindrome

You are given a string s of length n. Your task is to determine the minimum number of characters that need to be inserted at the beginning of s to make it a palindrome.

A string is considered a palindrome if it reads the same backward as forward. For example, the string "racecar" is already a palindrome whereas "abcb" is not.

Note: You are allowed to insert characters only at the front of the string. The characters inserted can be any characters, but the goal is to minimize the count of insertions required to transform the string into a palindrome.

For instance, if s = "abcb", by inserting 1 character ('b') at the beginning, the string becomes "babcb", which is a palindrome. Hence, the answer is 1.

inputFormat

The input consists of two lines:

• The first line contains an integer n representing the length of the string.
• The second line contains the string s itself.

You can assume that 1 ≤ n ≤ 10^5 and s consists of lowercase English letters.

outputFormat

Output a single integer which is the minimum number of characters that must be inserted at the beginning of the given string to make it a palindrome.

4
abcb

1