Given a string str, find the minimum characters to be added at front of the string to make it a palindrome.
Example 1:
Input:
str = ABCD
Output: 3
Explanation: The resultant string 
after adding 3 characters is DCBABCD.
The minimum possible answer is 3.
Example 2:
Input:
str = ABA
Output: 0
Explanation: The given string
is already a palindrome.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function addMinChar() which takes the string str as input parameters and returns the minimum number of characters to be added to make it a palindrome.
Expected Time Complexity: O(|str|)
Expected Auxiliary Space: O(|str|)
Constraints:
1 ≤  |str| ≤ 10^{5}
str contains only uppercase english alphabets

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def addMinChar (self, str1):

        # code here 

Solutions:
class Solution:

	def addMinChar(self, str1):
		size = len(str1)
		ans = 0
		i = 0
		j = size - 1
		while i <= j:
			if str1[i] == str1[j]:
				i += 1
				j -= 1
			else:
				ans += 1
				i = 0
				j = size - 1 - ans
		return ans


class Solution:

	def addMinChar(self, str1):
		ans = 0
		l = 0
		r = len(str1) - 1
		while l <= r:
			if str1[l] == str1[r]:
				l += 1
				r -= 1
			else:
				ans += 1
				l = 0
				r = len(str1) - 1 - ans
		return ans


class Solution:

	def addMinChar(self, str1):
		n = len(str1)
		i = 0
		count = 0
		j = n - 1
		while i < j:
			if str1[i] == str1[j]:
				i += 1
				j -= 1
			else:
				count += 1
				j = n - 1 - count
				i = 0
		return count


class Solution:

	def addMinChar(self, str1):
		a = 0
		l = 0
		n = len(str1) - 1
		while l <= n:
			if str1[l] == str1[n]:
				n -= 1
				l += 1
			else:
				a += 1
				l = 0
				n = len(str1) - 1 - a
		return a


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

class Solution:

	def addMinChar(self, str1):
		return len(str1) - lps(str1 + '#' + str1[::-1])


class Solution:

	def addMinChar(self, str1):
		n = len(str1)
		a = 0
		b = n - 1
		res = 0
		while a < b:
			if str1[a] == str1[b]:
				a += 1
				b -= 1
			else:
				res += 1
				a = 0
				b = n - res - 1
		return res


class Solution:

	def addMinChar(self, str1):
		n = len(str1)
		i = 0
		j = n - 1
		val = j
		res = 0
		while i < j:
			if str1[i] == str1[j]:
				i += 1
				j -= 1
				continue
			else:
				i = 0
				j = val - 1
				val = j
				res += 1
		return res


class Solution:

	def addMinChar(self, s):
		n = len(s)
		(l, r) = (0, n - 1)
		cnt = 0
		while l < r:
			if s[l] == s[r]:
				l += 1
				r -= 1
			else:
				cnt += 1
				l = 0
				r = n - cnt - 1
		return cnt


class Solution:

	def lpsarray(self, arr, lps, n):
		i = 1
		length = 0
		while i < n:
			if arr[i] == arr[length]:
				length += 1
				lps[i] = length
				i += 1
			elif length != 0:
				length = lps[length - 1]
			else:
				lps[i] = 0
				i += 1

	def addMinChar(self, str1):
		s = str1[::-1]
		str1 = str1 + s
		lps = [0] * (2 * len(s))
		self.lpsarray(str1, lps, 2 * len(s))
		return len(s) - lps[-1] if len(s) > lps[-1] else 0


class Solution:

	def addMinChar(self, str1):
		l = len(str1)
		m = 0
		for i in range(l, 1, -1):
			if self.isPal(str1[:i]):
				m = len(str1[:i])
				break
		if m == 0:
			return l - 1
		return l - m

	def isPal(self, str1):
		r = len(str1) - 1
		l = 0
		while l < r:
			if str1[l] == str1[r]:
				l += 1
				r -= 1
			else:
				return False
		return True


class Solution:

	def addMinChar(self, str1):
		l = len(str1) - 1
		f = 0
		count = 0
		eq = 0
		while f < l:
			if str1[f] == str1[l]:
				f += 1
				l -= 1
				eq += 1
			else:
				f = 0
				count += 1
				l = len(str1) - 1 - count
		return count


class Solution:

	def addMinChar(self, str1):
		length = len(str1)
		(start, end) = (0, length - 1)
		res = 0
		while start < end:
			if str1[start] == str1[end]:
				start += 1
				end -= 1
			else:
				res += 1
				start = 0
				end = length - res - 1
		return res


class Solution:

	def addMinChar(self, str1):
		rev = str1[::-1]
		s = str1 + '$' + rev
		n = len(s)
		length = 0
		lps = [0] * n
		i = 1
		while i < n:
			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 len(str1) - lps[n - 1]


class Solution:

	def addMinChar(self, s):
		nsame = 0
		same = 0
		ans = 0
		start = 0
		end = len(s) - 1
		while start < end:
			if s[start] != s[end]:
				ans += 1
				end = len(s) - 1 - ans
				start = 0
			else:
				start += 1
				end -= 1
		return ans


class Solution:

	def addMinChar(self, str1):
		i = 0
		j = len(str1) - 1
		cnt = 0
		while i < j:
			if str1[i] == str1[j]:
				i += 1
				j -= 1
			else:
				cnt += 1
				i = 0
				j = len(str1) - 1 - cnt
		return cnt


class Solution:

	def addMinChar(self, str1):
		start = 0
		end = len(str1) - 1
		add = 0
		while start < end:
			if str1[start] == str1[end]:
				start += 1
				end -= 1
			else:
				add += 1
				end = len(str1) - add - 1
				start = 0
		return add


class Solution:

	def addMinChar(self, str1):
		count = 0
		low = 0
		high = len(str1) - 1
		while low < high:
			if str1[low] == str1[high]:
				low += 1
				high -= 1
			else:
				low = 0
				count += 1
				high = len(str1) - 1 - count
		return count


class Solution:

	def addMinChar(self, str1):
		k = len(str1) - 1
		flag = True
		while k > 0 and flag:
			if k % 2 == 0:
				center = int(k / 2)
				i = k
				j = 0
				while str1[i] == str1[j]:
					j += 1
					i -= 1
					if i == j:
						return len(str1) - k - 1
						flag = False
						break
			else:
				left = 0
				right = k
				while str1[left] == str1[right]:
					left += 1
					right -= 1
					if left > right:
						return len(str1) - k - 1
						flag = False
						break
			k -= 1
			if k == 0:
				flag = False
				return len(str1) - 1


class Solution:

	def addMinChar(self, str1):
		s = str1
		s = s + '@' + s[::-1]
		n = len(s)
		l = [0] * n
		for i in range(1, n):
			j = l[i - 1]
			while j > 0 and s[i] != s[j]:
				j = l[j - 1]
			if s[i] == s[j]:
				j += 1
			l[i] = j
		return len(str1) - l[n - 1]


class Solution:

	def addMinChar(self, str1):
		rev = str1[::-1]
		new = str1 + '#' + rev

		def computed(s):
			li = [0] * len(s)
			(i, j) = (1, 0)
			while i < len(s):
				if s[i] == s[j]:
					li[i] = j + 1
					j += 1
					i += 1
				elif j != 0:
					j = li[j - 1]
				else:
					li[i] = 0
					i += 1
			return li
		k = computed(new)
		return len(str1) - k[-1]


class Solution:

	def addMinChar(self, str1):
		n = len(str1)
		for i in range(n):
			j = 0
			k = n - i - 1
			while j < k:
				if str1[j] != str1[k]:
					break
				j += 1
				k -= 1
			if j >= k:
				break
		return i


class Solution:

	def addMinChar(self, str1):
		startidx = count = 0
		endidx = len(str1) - 1
		while startidx < endidx:
			if str1[startidx] == str1[endidx]:
				startidx += 1
				endidx -= 1
			else:
				count += 1
				startidx = 0
				endidx = len(str1) - 1 - count
		return count


class Solution:

	def addMinChar(self, str1):
		n = len(str1)
		start = 0
		end = n - 1
		count = 0
		while start <= end:
			if str1[start] == str1[end]:
				start += 1
				end -= 1
			else:
				count += 1
				start = 0
				end = len(str1) - 1 - count
		return count


class Solution:

	def addMinChar(self, str1):

		def finder(s, k):
			mxfrm0 = 1
			for p in range(len(s)):
				i = p
				j = i + k
				l = 0
				while i >= 0 and j < len(s) and (s[i] == s[j]):
					l = j - i + 1
					i -= 1
					j += 1
				if i == -1:
					mxfrm0 = max(mxfrm0, l)
			return mxfrm0
		return len(str1) - max(finder(str1, 1), finder(str1, 2))


class Solution:

	def addMinChar(self, str1):
		res = 9999999999
		n = len(str1)
		for i in range(n):
			j1 = i
			j2 = i
			while j1 >= 0 and j2 < n:
				if str1[j1] != str1[j2]:
					break
				if j1 == 0:
					res = min(res, n - j2 - 1)
				j1 -= 1
				j2 += 1
			j1 = i
			j2 = i + 1
			while j1 >= 0 and j2 < n:
				if str1[j1] != str1[j2]:
					break
				if j1 == 0:
					res = min(res, n - j2 - 1)
				j1 -= 1
				j2 += 1
		return res


class Solution:

	def addMinChar(self, s):
		try:

			def finda(m, s, a):
				for i in range(m, 0, -1):
					if s[i] == a:
						return i
			n = len(s)
			o = s[0]
			a = m = finda(n - 1, s, s[0])
			b = 0
			while b < a:
				b += 1
				a -= 1
				if s[b] != s[a]:
					a = m = finda(m - 1, s, s[0])
					b = 0
			return n - m - 1
		except:
			return n - 1


class Solution:

	def addMinChar(self, str1):
		l = len(str1)
		add = ''
		i = 0
		j = l - 1
		while j >= 0:
			if str1[i] == str1[j]:
				a = i
				b = j
				d = False
				add = str1[j + 1:]
				while b >= a:
					d = False
					if str1[a] == str1[b]:
						a += 1
						b -= 1
						d = True
						continue
					break
				if d:
					return len(add)
				j -= 1
			else:
				j -= 1


class Solution:

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


class Solution:

	def addMinChar(self, str1):
		l = len(str1)
		s = 0
		e = l - 1
		count = 0
		while s < e:
			if str1[s] != str1[e]:
				count += 1
				s = 0
				e = l - count - 1
			else:
				s += 1
				e -= 1
		return count


class Solution:

	def addMinChar(self, str1):
		rev = str1[::-1]
		i = 0
		j = 0
		output = 0
		while i < len(str1):
			if rev[i] == str1[j]:
				i += 1
				j += 1
			else:
				output += 1
				i = output
				j = 0
		return output


from collections import Counter

class Solution:

	def cnt(self, ind, forw, str1):
		j = ind
		cnt = 0
		if forw:
			while j < len(str1) and str1[ind] == str1[j]:
				j += 1
				cnt += 1
			return cnt
		else:
			while j >= 0 and str1[ind] == str1[j]:
				j -= 1
				cnt += 1
			return cnt

	def addMinChar(self, str1):
		mp = Counter(str1)
		ind = (len(str1) - 2) // 2
		for i in range(len(str1) // 2):
			if mp[str1[i]] < 2:
				ind = i
				break
			mp[str1[i]] -= 1
		f1 = f2 = True
		ind2 = ind
		while ind2 >= 0:
			if not (len(str1) % 2 == 0 and ind2 == (len(str1) - 2) // 2):
				ev = ind2
				j = ind2 + 2
				while ev >= 0 and str1[ev] == str1[j]:
					ev -= 1
					j += 1
				if ev < 0:
					return len(str1) - j
			ev = ind2
			j = ind2 + 1
			while ev >= 0 and str1[ev] == str1[j]:
				ev -= 1
				j += 1
			if ev < 0:
				return len(str1) - j
			(cnt1, cnt2) = (self.cnt(ind2, 0, str1), self.cnt(ind2 + 1, 1, str1))
			if str1[ind2] == str1[ind2 + 1]:
				if cnt2 >= cnt1:
					ind2 -= max(1, cnt1)
				else:
					ind2 = ind2 - cnt1 + (cnt1 + cnt2) // 2
			else:
				ind2 -= 1
		return len(str1) - 1


class Solution:

	def addMinChar(self, str1):
		n = len(str1)
		s = str1[::-1]
		x = str1[0]
		for i in range(n):
			if s[i] == x:
				if str1[0:n - i] == s[i:]:
					return i
		return n - 1


class Solution:

	def addMinChar(self, str1):
		p = 0
		q = len(str1) - 1
		ans = 0
		while p <= q:
			if str1[p] != str1[q]:
				ans += 1
				p = 0
				q = len(str1) - 1 - ans
				continue
			p += 1
			q -= 1
		return ans