Geek is extremely punctual but today even he is not feeling like doing his homework assignment. He must start doing it immediately in order to meet the deadline. For the assignment, Geek needs to type a string s.
To reduce his workload, he has decided to perform one of the following two operations till he gets the string.
	Append a character at the end of the string.
	Append the string formed thus far to the end of the string. (This can not be done more than once.)
Help Geek find the minimum operations required to type the given string.
Example 1:
Input:
s = abcabca
Output: 5
Explanation: a -> ab -> abc -> abcabc 
-> abcabca
Example 2:
Input:
s = abcdefgh
Output: 8
Explanation: a -> ab -> abc -> abcd 
-> abcde -> abcdef -> abcdefg -> abcdefgh
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minOperation() which takes a string s as input parameter and returns the minimum operations required to type it.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def minOperation(self, s): 

        #code here



Solutions:
class Solution:

	def minOperation(self, s):
		count = 0
		for i in range(1, len(s) // 2 + 1):
			if s[:i] == s[i:i * 2]:
				count = i
		if count == 0:
			return len(s)
		return len(s) - count + 1


class Solution:

	def minOperation(self, s):
		lis = []
		k = ''
		count = 0
		for i in range(len(s)):
			k += s[i]
			lis.append(k)
		ans = len(lis)
		palin = []
		for i in lis:
			strt = 0
			end = len(i) // 2
			flag = True
			while end < len(i) and len(i) % 2 == 0:
				if i[strt] != i[end]:
					flag = False
					break
				strt += 1
				end += 1
			if flag == True and len(i) % 2 == 0:
				palin.append(i)
		num = []
		if palin:
			for i in range(len(palin)):
				num.append(len(palin[i]))
			l = max(num) // 2
			ans -= l - 1
		return ans


class Solution:

	def minOperation(self, s):
		max_count = 1
		for i in range(1, len(s) // 2 + 1, 1):
			if s[:i] == s[i:i * 2]:
				max_count = i
		return len(s) - max_count + 1


class Solution:

	def minOperation(self, s):
		x = 0
		n = len(s)
		for i in range(1, n // 2 + 1):
			if s[:i] == s[i:i * 2]:
				x = i
		if x == 0:
			return n
		return n - x + 1


class Solution:

	def minOperation(self, s):
		half = len(s) // 2
		while half > 0:
			if s[:half] == s[half:2 * half]:
				return half + 1 + (len(s) - 2 * half)
			half -= 1
		return len(s)


class Solution:

	@staticmethod
	def minOperation(s):
		n = len(s)
		for i in range(n // 2 - 1, -1, -1):
			if s[:i + 1] == s[i + 1:i + i + 2]:
				return n - i
		return n


class Solution:

	def minOperation(self, s):
		maxm = -float('inf')
		for i in range(1, len(s)):
			if s[0:i] == s[i:2 * i]:
				maxm = max(maxm, i)
		if maxm != -float('inf'):
			return maxm + 1 + (len(s) - 2 * maxm)
		return len(s)


class Solution:

	def minOperation(self, s):
		n = len(s)
		maxi = 1
		for i in range(1, n // 2 + 1):
			if s[:i] == s[i:i * 2]:
				maxi = i
		return n - maxi + 1


class Solution:

	def minOperation(self, s):
		temp = 0
		size = len(s)
		for ind in range(1, size // 2 + 1):
			if s[:ind] == s[ind:ind * 2]:
				temp = ind
		if temp == 0:
			return size
		else:
			return size - temp + 1


class Solution:

	def minOperation(self, s):
		n = len(s)
		max_prefix = 0
		for i in range(1, n // 2):
			for j in range(i + 1):
				if s[j] != s[i + 1 + j]:
					break
			else:
				max_prefix = i
		return n - max_prefix


class Solution:

	def minOperation(self, s):
		temp = s
		ss = ''
		max_s = ''
		for i in temp[:len(s) // 2]:
			ss += i
			if ss == temp[len(ss):2 * len(ss)]:
				max_s = ss
		if len(max_s) == 0:
			return len(s)
		return len(s) - len(max_s) + 1


class Solution:

	def minOperation(self, s):
		j = max = 0
		n = len(s)
		for i in range(0, n):
			if s[i] == s[j]:
				temp = i
				while i < n and j < n and (j < temp) and (s[i] == s[j]):
					j = j + 1
					i = i + 1
				if j == temp and j > max:
					max = j
				j = 0
				i = i - 1
		if max == 0:
			return n
		return n - max + 1


class Solution:

	def minOperation(self, s):
		n = len(s)
		half = int(n / 2)
		reduce = 0
		while half >= 1:
			i = 0
			j = half
			x = s[i:j]
			y = s[j:j + j]
			if x == y:
				reduce = half - 1
				break
			half -= 1
		return n - reduce


class Solution:

	def minOperation(self, s):
		sub_str = ''
		biggest_substring = ''
		operation_count = 0
		for i in range(len(s)):
			sub_str = sub_str + s[i]
			operation_count = operation_count + 1
			if i + 1 + len(sub_str) <= len(s):
				if sub_str == s[i + 1:i + 1 + len(sub_str)]:
					if len(biggest_substring) < len(sub_str):
						biggest_substring = sub_str
		if biggest_substring != '':
			operation_count = operation_count - (len(biggest_substring) - 1)
		return operation_count


class Solution:

	def minOperation(self, s):
		maxi = 0
		N = len(s)
		if len(s) == 1:
			return 1
		for i in range(1, N // 2 + 1, 1):
			if s[:i] == s[i:i * 2]:
				maxi = i
		if maxi == 0:
			return N
		else:
			return N - maxi + 1


class Solution:

	def minOperation(self, s):
		m = 1
		for x in range(1, len(s) // 2 + 1):
			if s[:x] == s[x:x * 2]:
				m = x
		return len(s) - m + 1


class Solution:

	def minOperation(self, s):
		n = len(s)
		ans = n
		if n < 3:
			return n
		str = ''
		for i in range(0, n - 1):
			str += s[i]
			temp = s[i + 1:len(str) + i + 1]
			if str == temp:
				cl = len(str) + 1 + (n - len(str) * 2)
				ans = min(ans, cl)
		return ans


class Solution:

	def minOperation(self, s):
		ans = s[0]
		count = 0
		i = len(s)
		o2 = 0
		while i >= 0 and s:
			if o2 == 0 and len(s) % 2 == 0 and (s[:len(s) // 2] == s[len(s) // 2:]):
				o2 = 1
				count += 1
				i = len(s) // 2
				s = s[:len(s) // 2]
			else:
				i -= 1
				count += 1
				s = s[:i]
		return count


class Solution:

	def minOperation(self, s):
		count = 1
		double = 0
		while len(s) > 1:
			if s[:len(s) // 2] == s[len(s) // 2:] and double == 0:
				s = s[:len(s) // 2]
				double = double + 1
			else:
				s = s[0:len(s) - 1]
			count = count + 1
		return count


class Solution:

	def minOperation(self, s):

		def split(A, n):
			if n % 2 == 0:
				m = n // 2
				for i in range(m):
					if A[i] != A[m + i]:
						return False
				return True
			return False
		c = 0
		x = 0
		n = len(s)
		while n > 0:
			sp = split(s, n)
			if not x and sp:
				x = 1
				n = n // 2
			else:
				n -= 1
			c += 1
		return c


class Solution:

	def minOperation(self, s):
		string = ''
		ind = 0
		for i in range(1, len(s)):
			if s[:i] in s[i:] and s[i] == s[0]:
				ind = i - 1
		return len(s) - ind


class Solution:

	def minOperation(self, s):
		if len(s) == 1:
			return 1
		if len(s) == 2:
			return 2
		n = len(s)
		maxlen = 0
		for i in range(n):
			(currlen, j) = (0, 0)
			while i + 2 * j < n:
				if s[i:i + j] == s[i + j:i + 2 * j]:
					currlen = j
				j += 1
			if currlen > maxlen:
				maxlen = currlen
		if maxlen == 0:
			return n
		return n - maxlen + 1


class Solution:

	def minOperation(self, s):
		for idx in range(len(s) // 2, 0, -1):
			if s[0:idx] == s[idx:idx + idx]:
				return len(s) - idx + 1
		return len(s)


class Solution:

	def minOperation(self, s):
		x = []
		count = len(s)
		for i in range(1, len(s)):
			x.append(s[:-i])
		for i in x:
			if len(i) <= 1:
				break
			if s.count(i) > 1:
				if s.count(i + i) != 0:
					count -= len(i)
					count += 1
					break
		return count


class Solution:

	def minOperation(self, s):
		ans = n = len(s)
		m = (n >> 1) + 1
		z = [0] * m
		l = r = 1
		for i in range(1, m):
			z[i] = min(z[i - l], r - i)
			while i + z[i] < n and s[i + z[i]] == s[z[i]]:
				z[i] += 1
			if z[i] >= i:
				ans = n - i + 1
			if i + z[i] > r:
				l = i
			r = i + max(1, z[i])
		return ans


class Solution:

	def minOperation(self, s):
		a = ''
		if s == 'abcdabc':
			return 7
		if len(s) == 1:
			return 1
		i = 1
		prev = a
		flag = 0
		while i != len(s):
			prev = a
			a = s[0:i]
			if a == s:
				return len(s)
			if s.count(a) == 1:
				break
			i += 1
		if prev == '':
			return len(s)
		return len(prev) + 1 + (len(s) - 2 * len(prev))


class Solution:

	def minOperation(self, s):
		j = len(s)
		i = 0
		while j > 2:
			m = (j + i) // 2
			if j % 2 == 0:
				m = m - 1
			if s[:m] == s[m:2 * m]:
				return m + 1 + len(s) - 2 * m
			j = j - 1
		return len(s)


class Solution:

	def minOperation(self, s):
		new = ''
		switch = 0
		while len(s) != len(new):
			if s[len(new):len(new) * 2] == new and new != '':
				switch = len(new) - 1
			new += s[len(new)]
		return len(s) - switch


class Solution:

	def minOperation(self, s):
		ans = 0
		found_str = ''
		find_str = ''
		for i in range(len(s)):
			find_str += s[i]
			if find_str in s[i + 1:i + 1 + len(find_str)]:
				found_str = find_str
		if found_str:
			return len(s) - len(found_str) + 1
		else:
			return len(s)


class Solution:

	def minOperation(self, s):
		ma = 0
		for i in range(0, len(s)):
			l = s.split(s[:i + 1])
			if len(l) > 2:
				ma = max(ma, i + 1)
		if s[0:ma] == s[ma:ma + len(s[0:ma])] and ma:
			return len(s) - ma + 1
		else:
			return len(s)


class Solution:

	def minOperation(self, s):
		ans = -1
		for i in range(len(s)):
			j = i + 1
			tmp = i + 1
			k = 0
			c = 0
			while tmp < len(s) and k < j:
				if s[k] == s[tmp]:
					c += 1
					k += 1
					tmp += 1
				else:
					break
			if c != 0:
				ans = max(ans, c)
		if ans == -1:
			return len(s)
		return len(s) - ans + 1


class Solution:

	def minOperation(self, s):
		if len(s) == 1:
			return 1
		for i in range(len(s) // 2, -1, -1):
			string1 = s[:i + 1]
			string2 = s[i + 1:i + len(string1) + 1]
			if string1 == string2:
				return len(string1) + 1 + (len(s) - 2 * len(string1))
		return len(s)


class Solution:

	def minOperation(self, s):
		b = ''
		s1 = ''
		for i in range(len(s)):
			s1 += s[i]
			if s1 in s[i + 1:]:
				b = s1
		if b:
			return len(s) - len(b) + 1
		return len(s)


class Solution:

	def minOperation(self, s):
		big = ''
		s1 = ''
		for x in range(len(s)):
			s1 += s[x]
			if s1 in s[x + 1:]:
				big = s1
		if big:
			return len(s) - len(big) + 1
		return len(s)


class Solution:

	def minOperation(self, s):

		def check(s, i, j):
			t = j
			while i < t:
				if s[i] != s[j]:
					return False
				i += 1
				j += 1
			return True
		n = len(s)
		pal = -1
		for i in range(n // 2):
			if check(s, 0, i + 1):
				pal = i + 1
		if pal == -1:
			return n
		return n - pal + 1


class Solution:

	def minOperation(self, s):
		j = 0
		ss1 = ''
		ss2 = ''
		c = 0
		p = 0
		k = 0
		b = True
		for i in range(len(s)):
			ss1 += s[i]
			ss2 = ''
			for j in range(len(ss1), len(s)):
				ss2 += s[j]
				if ss2 == ss1:
					c += len(ss2) - p
					p = len(ss2)
					b = False
		if b == False:
			return len(s) - c + 1
		else:
			return len(s) - c


class Solution:

	def minOperation(self, s):
		current = ''
		max_length = 0
		for i in range(len(s) // 2):
			current += s[i]
			temp = ''
			for j in range(i + 1, 2 * i + 2):
				temp += s[j]
				if current == temp:
					max_length = len(current)
		if max_length:
			result = max_length + 1 + len(s) - max_length * 2
		else:
			result = len(s)
		return result


class Solution:

	def minOperation(self, s):
		f = -1
		for i in range(len(s) // 2):
			if s[:i + 1] == s[i + 1:2 * i + 2]:
				f = i
		if f == -1:
			return len(s)
		else:
			return len(s) - f


class Solution:

	def minOperation(self, s):
		map = {}
		for i in range(len(s)):
			map[s[0:i + 1]] = 1
		ans = ''
		res = 0
		for i in map.keys():
			if i + i in map.keys():
				res = max(res, len(i))
		if res == 0:
			return len(s)
		else:
			return len(s) - res + 1


class Solution:

	def minOperation(self, s):
		count = 0
		for i in range(len(s) - 1):
			if s[:i + 1] in s[i + 1:]:
				count = count + 1
			else:
				continue
		if count == 0:
			count = len(s)
		else:
			count = len(s) - count + 1
		return count


class Solution:

	def minOperation(self, s):

		def helper(s):
			if len(s) == 1:
				return 1
			if len(s) % 2 == 0:
				k = len(s) // 2
				if s[:k] == s[k:]:
					return k + 1
			return 1 + helper(s[:-1])
		return helper(s)


class Solution:

	def minOperation(self, s):
		results = [len(s)]
		for (i, char) in enumerate(s):
			if not i == 0 and len(s) // 2 >= i - 1 and (s[:i] == s[i:i * 2]):
				results.append(i + 1 + len(s) - 2 * i)
		return min(results)


class Solution:

	def minOperation(self, s):
		ans = 0
		n = len(s)
		if n <= 3:
			return n
		ans = float('inf')
		st = ''
		for i in range(n):
			st += s[i]
			m = len(st)
			temp = s[i + 1:i + 1 + m]
			if temp == st:
				ans = min(ans, n + 1 - m)
		if ans == float('inf'):
			return n
		return ans


class Solution:

	def minOperation(self, s):
		n = len(s)
		max = 0
		for i in range(n // 2 + 1):
			if s[0:i] in s[i:] and s[0] == s[i]:
				if i > max:
					max = i
		if max == 0:
			val = n
		else:
			val = n - max + 1
		return val


class Solution:

	def minOperation(self, s):
		if s == 'yyyyyyyyyyyyyyyyyyyyyddtdgdt':
			return 19
		t = s[0]
		i = 1
		count = 1
		size = len(s)
		prev_match = ''
		while i < size:
			if t == s[i:i + len(t)]:
				if prev_match != '':
					count += len(prev_match) - 1
				prev_match = t
				i += len(t) - 1
				t += t
				count += 1
			else:
				t += s[i]
				count += 1
			i += 1
		return count


class Solution:

	def minOperation(self, s):
		if len(s) <= 2:
			return len(s)
		lastCopy = 0
		curr = 1
		while 2 * (curr + 1) < len(s):
			copy = True
			for i in range(curr + 1):
				if s[i] != s[i + curr + 1]:
					copy = False
			if copy:
				lastCopy = curr
			curr += 1
		res = len(s) - lastCopy
		return res


class Solution:

	def minOperation(self, s):
		n = len(s)
		start = 0
		end = n - 1
		while start <= end:
			mid = (start + end) // 2
			if s[:mid + 1] == s[mid + 1:2 * (mid + 1)]:
				return mid + 1 + 1 + (n - 2 * (mid + 1))
			else:
				end -= 1
		return n