Geek wants to send an encrypted message in the form of string S to his friend Keeg along with instructions on how to decipher the message. To decipher the message, his friend needs to iterate over the message string from left to right, if he finds a '*', he must remove it and add all the letters read so far to the string. He must keep on doing this till he gets rid of all the '*'.
Can you help Geek encrypt his message string S? 
Note: If the string can be encrypted in multiple ways, find the smallest encrypted string. 
Example 1:
Input: S = "ababcababcd"
Output: ab*c*d
Explanation: We can encrypt the string 
in following way : "ababcababcd" -> 
"ababc*d" -> "ab*c*d"
Example 2:
Input: S = "zzzzzzz"
Output: z*z*z
Explanation: The string can be encrypted 
in 2 ways: "z*z*z" and "z**zzz". Out of 
the two "z*z*z" is smaller in length.
Your Task: 
You don't need to read input or print anything. Complete the function secretCipher() which takes the message string S as input parameter and returns the shortest possible encrypted string.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints: 
1 ≤ |S| ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def compress(self, s):
        # Your code goes here

Solutions:
class Solution:

	def fillarray(self, s, a):
		a[0] = 0
		for i in range(1, len(s)):
			series = a[i - 1]
			while series:
				if s[series] == s[i]:
					a[i] = series + 1
					break
				series = a[series - 1]
			if series == 0:
				a[i] = int(s[i] == s[0])
		return a

	def compress(self, s):
		a = [0] * len(s)
		a = self.fillarray(s, a)
		shortened = []
		n = len(s)
		i = n - 1
		while i > 0:
			if i % 2 == 0:
				shortened.append(s[i])
				i = i - 1
				continue
			star_here = False
			suffix = a[i]
			substrlen = i + 1
			if suffix * 2 >= substrlen:
				if substrlen % (substrlen - suffix) == 0:
					if substrlen / (substrlen - suffix) % 2 == 0:
						star_here = True
			if star_here == True:
				shortened.append('*')
				i = i // 2 + 1
			else:
				shortened.append(s[i])
			i = i - 1
		ret = ''
		ret = ret + s[0]
		n = len(shortened)
		while n:
			ret = ret + shortened[n - 1]
			shortened.pop()
			n = n - 1
		return ret


class Solution:

	def compress(self, s):
		hash = {}
		ans = 0
		for i in range(len(s)):
			ans += ord(s[i]) - ord('a')
			hash[i] = ans
		ans = ''
		last_ind = len(s) - 1
		while last_ind != -1:
			if last_ind % 2 == 0:
				ans += s[last_ind]
				last_ind -= 1
			else:
				half = last_ind // 2
				second_half_hash = hash[last_ind] - hash[half]
				first_half_hash = hash[half]
				if first_half_hash == second_half_hash:
					if s[:half + 1] == s[half + 1:last_ind + 1]:
						ans += '*'
						last_ind = half
					else:
						ans += s[last_ind]
						last_ind -= 1
				else:
					ans += s[last_ind]
					last_ind -= 1
		return ans[::-1]


p = 31
mod = 10 ** 9 + 7
po = [1 for i in range(10 ** 5 + 1)]
for i in range(1, len(po)):
	po[i] = po[i - 1] * p % mod

class Solution:

	def compress(self, s):
		has = [0 for i in range(len(s) + 1)]
		for i in range(1, len(s) + 1):
			has[i] = (has[i - 1] + (ord(s[i - 1]) - ord('a') + 1) * po[i]) % mod
		res = ''
		i = len(s)
		while i > 0:
			if i % 2:
				res = res + s[i - 1]
				i -= 1
			else:
				a = has[i // 2]
				b = (has[i] - a + mod) % mod
				if a * po[i // 2] % mod == b:
					res += '*'
					i //= 2
				else:
					res += s[i - 1]
					i -= 1
		return res[::-1]


class Solution:

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

	def compress(self, s):
		a = self.helper(s)
		n = len(s)
		ans = ''
		i = n - 1
		while i > 0:
			if i % 2 == 0:
				ans += s[i]
				i -= 1
				continue
			flag = False
			suffix = a[i]
			substr = i + 1
			if suffix * 2 >= substr:
				if substr % (substr - suffix) == 0:
					if substr / (substr - suffix) % 2 == 0:
						flag = True
			if flag:
				ans += '*'
				i = i // 2 + 1
			else:
				ans += s[i]
			i -= 1
		return s[0] + ans[::-1]


class Solution:

	def compress(self, s):
		n = len(s)
		dp = [0 for _ in range(n)]
		(left, right) = (0, 1)
		while right < n:
			if s[left] == s[right]:
				dp[right] = 1 + left
				left += 1
				right += 1
			elif left:
				left = dp[left - 1]
			else:
				right += 1
		k = n - 1
		ans = ''
		while k:
			if k % 2 == 0:
				ans += s[k]
				k -= 1
				continue
			flag = False
			suffix = dp[k]
			substr = k + 1
			if 2 * suffix >= substr and substr % (substr - suffix) == 0 and (substr // (substr - suffix) % 2 == 0):
				flag = True
			if flag:
				ans += '*'
				k = k // 2 + 1
			else:
				ans += s[k]
			k -= 1
		return s[0] + ans[::-1]


class Solution:

	def compress(self, s):

		def getlps(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
				elif l > 0:
					l = lps[l - 1]
				else:
					lps[i] = 0
					i += 1
			return lps
		arr = getlps(s)
		n = len(s)
		ans = ''
		j = n - 1
		while j > 0:
			if j % 2 == 0:
				ans += s[j]
				j -= 1
				continue
			flag = False
			suff = arr[j]
			substr = j + 1
			if suff * 2 >= substr:
				if substr % (substr - suff) == 0:
					if substr / (substr - suff) % 2 == 0:
						flag = True
			if flag:
				ans += '*'
				j = j // 2 + 1
			else:
				ans += s[j]
			j -= 1
		return s[0] + ans[::-1]


class Solution:

	def compress(self, s):
		(lps, i, j) = ([0] * len(s), 1, 0)
		while i < len(s):
			if s[i] == s[j]:
				(lps[i], i, j) = (j + 1, i + 1, j + 1)
			elif j > 0:
				j = lps[j - 1]
			else:
				(lps[i], i) = (0, i + 1)
		a = []
		i = len(s) - 1
		while i >= 0:
			if i % 2 == 1 and lps[i] >= (i + 1) // 2 and ((i + 1) % (2 * (i + 1 - lps[i])) == 0):
				a.append('*')
				i -= (i + 1) // 2
			else:
				a.append(s[i])
				i -= 1
		return ''.join(a[::-1])


class Solution:

	def compress(self, s):
		n = len(s)
		lps = [0] * n
		lps[0] = 0
		for i in range(1, n):
			j = lps[i - 1]
			while j > 0 and s[i] != s[j]:
				j = lps[j - 1]
			if s[i] == s[j]:
				j += 1
			lps[i] = j
		ans = ''
		i = n - 1
		while i > 0:
			if i % 2 == 0:
				ans += s[i]
				i -= 1
				continue
			suff = lps[i]
			subln = i + 1
			flag = False
			if suff * 2 >= subln:
				if subln % (subln - suff) == 0:
					if subln / (subln - suff) % 2 == 0:
						flag = True
			if flag:
				ans += '*'
				i = i // 2 + 1
			else:
				ans += s[i]
			i -= 1
		return s[0] + ans[::-1]


class Solution:

	def compress(self, s):
		n = len(s)
		pi = [0] * n
		j = 0
		for i in range(1, n):
			while j and s[i] != s[j]:
				j = pi[j - 1]
			if s[i] == s[j]:
				j += 1
			pi[i] = j
		res = []
		i = n - 1
		while i >= 0:
			if i % 2 and pi[i] >= (i + 1) // 2 and ((i + 1) % (2 * (i + 1 - pi[i])) == 0):
				res.append('*')
				i = (i + 1) // 2
			else:
				res.append(s[i])
			i -= 1
		return ''.join(res[::-1])