Given string str of length N. The task is to find the minimum characters to be added at the front to make string palindrome.
Note: A palindrome is a word which reads the same backward as forward. Example: "madam".
Example 1:
Input:
S = "abc"
Output: 2
Explanation: 
Add 'b' and 'c' at front of above string to make it
palindrome : "cbabc"
Example 2:
Input:
S = "aacecaaa"
Output: 1
Explanation: Add 'a' at front of above string
to make it palindrome : "aaacecaaa"
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minChar() which takes a string S and returns an integer as output.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= S.length <= 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Starter code: class Solution:

    def minChar(self,str):

        #Write your code here

Solutions:
class Solution:

	def minChar(self, str):
		ha = [0] * len(s)
		(i, j) = (0, len(s) - 1)
		ans = 0
		while i < j:
			if s[i] == s[j]:
				if i == 0:
					ha[i] = 1
				else:
					ha[i] = 1 + ha[i - 1]
				i += 1
				j -= 1
			elif i == 0:
				ans = len(s) - j
				j -= 1
			else:
				i = ha[i - 1] // 2
				ans = len(s) - (j + 1) - i
		return ans


class Solution:

	def minChar(self, string):
		my_str = string + '@' + string[::-1]
		first = 0
		second = 2
		my_str = ' ' + my_str
		lps_arr = [0] * len(my_str)
		while second < len(my_str):
			if my_str[first + 1] == my_str[second]:
				lps_arr[second] = first + 1
				first += 1
				second += 1
			elif first != 0:
				first = lps_arr[first]
			else:
				second += 1
		return len(string) - lps_arr[-1]


class Solution:

	def minChar(self, s):

		def lps(text):
			lps = [0] * len(text)
			j = 0
			for i in range(1, len(text)):
				while j > 0 and text[i] != text[j]:
					j = lps[j - 1]
				if text[i] == text[j]:
					j += 1
				lps[i] = j
			return lps
		s = s + '#' + s[::-1]
		lps = lps(s)
		return (len(s) - 1) // 2 - lps[-1]


class Solution:

	def minChar(self, str1):

		def compute_lps_array(string, size):
			length = 0
			lps = [0] * size
			i = 1
			while i < size:
				if string[i] == string[length]:
					length += 1
					lps[i] = length
					i += 1
				elif length != 0:
					length = lps[length - 1]
				else:
					lps[i] = 0
					i += 1
			return lps
		reverse_s = s[::-1]
		concat = s + '$' + reverse_s
		lps = compute_lps_array(concat, len(concat))
		return len(s) - lps[-1]


class Solution:

	def minChar(self, str):
		n = len(s)
		r = s[::-1]
		lps = [0] * (n + 1)
		(i, length) = (0, 0)
		while i < n:
			if r[i] == s[length]:
				length += 1
				lps[i + 1] = length
				i += 1
			elif length == 0:
				lps[i + 1] = 0
				i += 1
			else:
				length = lps[length - 1]
		return n - lps[-1]


class Solution:

	def minChar(self, string):

		def computeLPSArray(string):
			M = len(string)
			lps = [None] * M
			length = 0
			lps[0] = 0
			i = 1
			while i < M:
				if string[i] == string[length]:
					length += 1
					lps[i] = length
					i += 1
				elif length != 0:
					length = lps[length - 1]
				else:
					lps[i] = 0
					i += 1
			return lps
		revStr = string[::-1]
		concat = string + '$' + revStr
		lps = computeLPSArray(concat)
		return len(string) - lps[-1]


class Solution:

	def computeLPS(self, needle):
		if needle == '':
			return 0
		lps = [0] * len(needle)
		(prevLPS, i) = (0, 1)
		while i < len(needle):
			if needle[i] == needle[prevLPS]:
				lps[i] = prevLPS + 1
				prevLPS += 1
				i += 1
			elif prevLPS == 0:
				lps[i] = 0
				i += 1
			else:
				prevLPS = lps[prevLPS - 1]
		return lps

	def minChar(self, str):
		revStr = str[::-1]
		concat = str + '$' + revStr
		lps = self.computeLPS(concat)
		return len(str) - lps[-1]


class Solution:

	def is_palin(self, s):
		start = 0
		end = len(s) - 1
		while start < end:
			if s[start] != s[end]:
				return False
			start += 1
			end -= 1
		return True

	def minChar(self, str):
		n = len(str)
		temp = str + '$' + str[::-1]
		l = n + n + 1
		lps = [0] * l
		i = 1
		j = 0
		while i < l:
			if temp[i] == temp[j]:
				lps[i] = j + 1
				i += 1
				j += 1
			elif j == 0:
				i += 1
			else:
				j = lps[j - 1]
		ans = n - lps[l - 1]
		return ans


class Solution:

	def minChar(self, str):
		s = str
		revStr = s[::-1]
		concat = s + '$' + revStr
		n = len(concat)
		lps = [0] * n
		lps = computeLPSArray(concat, n, lps)
		return len(s) - lps[-1]

def computeLPSArray(pat, n, lps):
	len = 0
	lps[0]
	i = 1
	while i < n:
		if pat[i] == pat[len]:
			len += 1
			lps[i] = len
			i += 1
		elif len != 0:
			len = lps[len - 1]
		else:
			lps[i] = 0
			i += 1
	return lps


class Solution:

	def compute_lps_array(self, s: str):
		n = len(s)
		lps = [0] * n
		(i, l) = (1, 0)
		lps[0] = 0
		while i < n:
			if s[i] == s[l]:
				l += 1
				lps[i] = l
				i += 1
			elif l != 0:
				l = lps[l - 1]
			else:
				lps[i] = 0
				i += 1
		return lps

	def minChar(self, str):
		str_concat = str + '$' + str[::-1]
		lps = self.compute_lps_array(str_concat)
		return len(str) - lps[len(str_concat) - 1]


class Solution:

	def conlsparr(self, str):
		M = len(str)
		lsp = [None] * M
		length = 0
		lsp[0] = 0
		i = 1
		while i < M:
			if str[i] == str[length]:
				length += 1
				lsp[i] = length
				i += 1
			elif length != 0:
				length = lsp[length - 1]
			else:
				lsp[i] = 0
				i += 1
		return lsp

	def minChar(self, str):
		revstr = str[::-1]
		concat = str + '$' + revstr
		lsp1 = self.conlsparr(concat)
		return len(str) - lsp1[-1]


class Solution:

	def minChar(self, s):
		res = []
		li = list(s)
		li.append('$')
		li.extend(list(s[::-1]))
		lps = [0] * len(li)
		i = 1
		prev = 0
		while i < len(li):
			if li[i] == li[prev]:
				prev = prev + 1
				lps[i] = prev
				i = i + 1
			elif prev == 0:
				lps[i] = 0
				i = i + 1
			else:
				prev = lps[prev - 1]
		return len(s) - lps[-1]


class Solution:

	def genLPS(self, str):
		n = len(str)
		lps = [0] * n
		j = 1
		length = 0
		while j < n:
			if str[j] == str[length]:
				length += 1
				lps[j] = length
				j += 1
			elif length != 0:
				length = lps[length - 1]
			else:
				lps[j] = 0
				j += 1
		return lps[-1]

	def minChar(self, str):
		n = len(str)
		str = str + '%' + str[::-1]
		return n - self.genLPS(str)


class Solution:

	def getlps(self, s):
		n = len(s)
		lps = [0] * n
		i = 1
		l = 0
		while i < n:
			if s[i] == s[l]:
				l += 1
				lps[i] = l
				i += 1
			else:
				if l == 0:
					lps[i] = 0
					i += 1
				l = lps[l - 1]
		return lps

	def minChar(self, str):
		str2 = str[::-1]
		n = len(str)
		S = str + '$' + str2
		c = self.getlps(S)
		return n - c[-1]


class Solution:

	def minChar(self, s):
		newstr = s + '$' + s[::-1]
		lps = [0] * len(newstr)
		(prevlps, i) = (0, 1)
		while i < len(newstr):
			if newstr[prevlps] == newstr[i]:
				prevlps += 1
				lps[i] = prevlps
				i += 1
			elif prevlps == 0:
				lps[i] = 0
				i += 1
			else:
				prevlps = lps[prevlps - 1]
		return len(s) - lps[-1]


class Solution:

	def minChar(self, str):
		newStr = str + '$' + str[::-1]
		lps = [0] * len(newStr)
		self.findlps(lps, newStr)
		return len(str) - lps[-1]

	def findlps(self, lps, a):
		i = 0
		j = 1
		while i <= j and j < len(a):
			if a[i] == a[j]:
				i += 1
				lps[j] = i
				j += 1
			elif i != 0:
				i = lps[i - 1]
			else:
				j += 1


class Solution:

	def minChar(self, str1):
		rev = str1[::-1]
		concat = str1 + '$' + rev
		lps = self.addMinChar(concat)
		return len(str1) - lps[-1]

	def addMinChar(self, str1):
		m = len(str1)
		lps = [None] * m
		length = 0
		lps[0] = 0
		i = 1
		while i < m:
			if str1[i] == str1[length]:
				length += 1
				lps[i] = length
				i += 1
			elif length != 0:
				length = lps[length - 1]
			else:
				lps[i] = 0
				i += 1
		return lps


class Solution:

	def minChar(self, str):
		x = list(str)
		x.append('$')
		x.extend(list(str[::-1]))
		lps = [0] * len(x)
		i = 1
		prev = 0
		while i < len(x):
			if x[prev] == x[i]:
				prev = prev + 1
				lps[i] = prev
				i = i + 1
			elif prev == 0:
				lps[i] = 0
				i = i + 1
			else:
				prev = lps[prev - 1]
		return len(str) - lps[-1]
		return 0


class Solution:

	def computeLPSArray(self, s):
		lps = [None] * len(s)
		lps[0] = 0
		length = 0
		i = 1
		M = len(s)
		while i < M:
			if s[i] == s[length]:
				length += 1
				lps[i] = length
				i += 1
			elif length != 0:
				length = lps[length - 1]
			else:
				lps[i] = 0
				i += 1
		return lps

	def minChar(self, str):
		s = str + '$' + str[::-1]
		lps = self.computeLPSArray(s)
		return len(str) - lps[-1]


class Solution:

	def minChar(self, str):
		n = len(str)
		req = 0
		(l, r) = (0, n - 1)
		if str[l] == str[r]:
			while l < r and str[r] == str[n - 1]:
				if str[l] == str[r]:
					l += 1
				else:
					req += 1
				r -= 1
		while l < r:
			if str[l] == str[r]:
				l += 1
			else:
				req = n - r
				l = 0
			r -= 1
		return req


class Solution:

	def minChar(self, str):
		z = 0
		i = 1
		lps = [0]
		v = str[::-1]
		str = str + '$' + v
		while i < len(str):
			if str[i] == str[z]:
				z = z + 1
				lps.append(z)
				i = i + 1
			elif z != 0:
				z = lps[z - 1]
			else:
				lps.append(0)
				i = i + 1
		return len(v) - lps[-1]


class Solution:

	def minChar(self, str):
		l = 0
		r = len(str) - 1
		res = 0
		while l < r:
			if str[l] == str[r]:
				l += 1
				r -= 1
			else:
				res += 1
				if l != 0:
					l -= 1
					r += 1
				r -= 1
		return res


class Solution:

	def minChar(self, s):
		ans = 0
		i = 0
		j = len(s) - 1
		while i < j:
			if s[i] == s[j]:
				i += 1
			else:
				ans += 1
				if i != 0:
					j += 1
					i -= 1
			j -= 1
		return ans


class Solution:

	def minChar(self, str):

		def lps(s):
			i = 1
			l = 0
			lps = [0] * len(s)
			while i < len(s):
				if s[i] == s[l]:
					l = l + 1
					lps[i] = l
					i = i + 1
				elif l != 0:
					l = lps[l - 1]
				else:
					lps[i] = 0
					i = i + 1
			return lps
		length = len(str)
		str_a = str + '#' + str[::-1]
		a = lps(str_a)
		return length - a[-1]


class Solution:

	def minChar(self, s):
		r = s[::-1]
		lps = [0] * (len(s) + 1)
		(i, j) = (0, 0)
		while i < len(s):
			if r[i] == s[j]:
				j += 1
				lps[i + 1] = j
				i += 1
			elif j == 0:
				lps[i + 1] = 0
				i += 1
			else:
				j = lps[j - 1]
		return len(s) - lps[-1]


class Solution:

	def minChar(self, str):
		B = str + '$' + str[::-1]
		LPS = [0] * len(B)
		(prevLPS, i) = (0, 1)
		while i < len(B):
			if B[i] == B[prevLPS]:
				LPS[i] = prevLPS + 1
				i += 1
				prevLPS += 1
			elif prevLPS == 0:
				LPS[i] = prevLPS
				i += 1
			else:
				prevLPS = LPS[prevLPS - 1]
		return len(str) - LPS[-1]


class Solution:

	def minChar(self, str):
		new_string = str + '#' + str[::-1]
		pattern = self.get_pattern(new_string)
		return len(str) - pattern[-1] - 1

	def get_pattern(self, substring):
		pattern = [-1] * len(substring)
		j = 0
		i = 1
		while i < len(substring):
			if substring[i] == substring[j]:
				pattern[i] = j
				i += 1
				j += 1
			elif j > 0:
				j = pattern[j - 1] + 1
			else:
				i += 1
		return pattern


class Solution:

	def lps(self, str1):
		i = 1
		j = 0
		pi = [0 for i in range(len(str1))]
		while i < len(str1):
			if str1[i] == str1[j]:
				pi[i] = j + 1
				i += 1
				j += 1
			elif j == 0:
				i += 1
			else:
				j = pi[j - 1]
		return pi[-1]

	def minChar(self, str):
		revS = str[::-1]
		str1 = str + '$' + revS
		ans = self.lps(str1)
		return len(str) - ans


class Solution:

	def minChar(self, s):
		concat = s + s[::-1]
		res = self.lps(concat)
		return len(s) - res[-1]

	def lps(self, a):
		i = 1
		j = 0
		lps = []
		lps.append(0)
		while i < len(a):
			if a[i] == a[j]:
				lps.append(j + 1)
				i += 1
				j += 1
			elif j == 0:
				lps.append(0)
				i += 1
			else:
				j = lps[j - 1]
		return lps


class Solution:

	def lps(s):
		n = len(s)
		lps = [0] * n
		lenn = 0
		i = 1
		while i < n:
			if s[lenn] == s[i]:
				lenn += 1
				lps[i] = lenn
				i += 1
			elif lenn != 0:
				lenn = lps[lenn - 1]
			else:
				lps[i] = 0
				i += 1
		return lps

	def minChar(self, s):
		n = len(s)
		if n == 1:
			return 0
		revS = s[::-1]
		concat = s + '$' + revS
		ls = Solution.lps(concat)
		return len(s) - ls[-1]


class Solution:

	def minChar(self, s):
		on = len(s)
		s = s + '$' + s[::-1]
		n = len(s)
		lps = [0] * n

		def preProcess():
			j = 0
			i = 1
			while i < n:
				if s[i] == s[j]:
					lps[i] = j + 1
					i += 1
					j += 1
				elif j > 0:
					j = lps[j - 1]
				else:
					i += 1
		preProcess()
		return on - lps[-1]


class Solution:

	def LPSSTRING(self, String):
		i = 1
		M = len(String)
		lps = [None] * M
		lps[0] = 0
		length = 0
		while i < M:
			if String[i] == String[length]:
				length += 1
				lps[i] = length
				i += 1
			elif length != 0:
				length = lps[length - 1]
			else:
				lps[i] = 0
				i += 1
		return lps

	def minChar(self, str):
		String = str + '$' + str[::-1]
		LPS = self.LPSSTRING(String)
		return len(str) - LPS[-1]


class Solution:

	def Concat(self, string):
		M = len(string)
		i = 1
		length = 0
		lps = [None] * M
		lps[0] = 0
		while i < M:
			if string[i] == string[length]:
				length += 1
				lps[i] = length
				i += 1
			elif length != 0:
				length = lps[length - 1]
			else:
				lps[i] = 0
				i += 1
		return lps

	def minChar(self, str):
		string = str + '$' + str[::-1]
		lps = self.Concat(string)
		return len(str) - lps[-1]


class Solution:

	def create_lps(self, A):
		M = len(A)
		lps = [None] * M
		l = 0
		lps[0] = l
		i = 1
		while i < M:
			if A[i] == A[l]:
				l += 1
				lps[i] = l
				i += 1
			elif l != 0:
				l = lps[l - 1]
			else:
				lps[i] = 0
				i += 1
		return lps

	def minChar(self, A):
		lps = self.create_lps(A + '$' + A[::-1])
		return len(A) - lps[-1]


def lps(s):
	n = len(s)
	LPS = [0] * n
	i = 1
	j = 0
	while i < n:
		if s[i] == s[j]:
			j += 1
			LPS[i] = j
			i += 1
		elif j != 0:
			j = LPS[j - 1]
		else:
			LPS[i] = 0
			i += 1
	return LPS

class Solution:

	def minChar(self, s):
		a = s + '$' + s[::-1]
		LPS = lps(a)
		ans = len(s) - LPS[-1]
		return ans


class Solution:

	def minChar(self, str):
		rev = str[::-1]
		new = str + rev
		n = len(str)
		lps = [0] * len(new)
		i = 1
		h = 0
		while i < 2 * n:
			if new[i] == new[h]:
				lps[i] += 1
				i += 1
				h += 1
			elif h > 0:
				h = lps[h - 1]
			elif h == 0:
				lps[i] = 0
				i += 1
		if h > n:
			h = math.floor(h) / 2
		ans = n - h
		return ans