Given a string S, check if it is possible to construct the given string S by performing any of the below operations any number of times. In each step, we can:
	Add any character at the end of the string.
	or, append the string to the string itself.
The above steps can be applied any number of times. The task is to find the minimum steps required to form the string.
Example 1:
Input: S = "aaaaaaaa"
Output: 4
Explanation: 
move 1: add 'a' to form "a"
move 2: add 'a' to form "aa"
move 3: append "aa" to form "aaaa"
move 4: append "aaaa" to form "aaaaaaaa"
Ã¢â¬â¹Example 2:
Input: S = "abcabca"
Output: 5
Explanation: 
move 1: add 'a' to form "a"
move 2: add 'b' to form "ab"
move 3: add 'c' to form "abc"
move 4: append "abc" to form "abcabc"
move 5: add 'a' to form "abcabca"
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minSteps() which takes the string s as inputs and returns the answer.
Expected Time Complexity: O(|S|^{2})
Expected Auxiliary Space: O(|S|)
Constraints:
1 ≤ |S| ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3
class Solution:
	def minSteps(self, S):
		# code here

Solutions:
class Solution:

	def minSteps(self, S):
		dp = [100000000] * len(S)
		dp[0] = 1
		for i in range(1, len(S)):
			if i % 2 == 1 and S[:i // 2 + 1] == S[i // 2 + 1:i + 1]:
				dp[i] = min(1 + dp[i // 2], dp[i])
			dp[i] = min(dp[i], dp[i - 1] + 1)
		return dp[len(S) - 1]


class Solution:

	def minSteps(self, S):
		return self.helper(S[0], S, {}) + 1

	def helper(self, input, output, store):
		if input == output:
			return 0
		n = len(input)
		if input != output[:n]:
			return float('inf')
		if input in store:
			return store[input]
		add = self.helper(input + output[n], output, store)
		double = self.helper(input + input, output, store)
		store[input] = min(add, double) + 1
		return store[input]


class Solution:

	def minSteps(self, s):
		n = len(s)
		dp = [0] * n
		dp[0] = 1
		for i in range(1, n):
			x = dp[i - 1] + 1
			y = float('inf')
			mid = (i + 1) // 2
			if i % 2 != 0 and s[0:mid] == s[mid:mid + mid]:
				y = min(y, dp[i // 2] + 1)
			dp[i] = min(x, y)
		return dp[n - 1]


INT_MAX = 100000000

class Solution:

	def minSteps(self, S):
		dp = [INT_MAX for i in range(len(S))]
		s1 = ''
		s2 = ''
		dp[0] = 1
		s1 += S[0]
		for i in range(1, len(S)):
			s1 += S[i]
			s2 = S[i + 1:i + 1 + i + 1]
			dp[i] = min(dp[i], dp[i - 1] + 1)
			if s1 == s2:
				dp[i * 2 + 1] = min(dp[i * 2 + 1], dp[i] + 1)
		return dp[len(S) - 1]


class Solution:

	def minSteps(self, S):
		n = len(S)
		s1 = ''
		s2 = ''
		td = [10000 for _ in range(n)]
		s1 += S[0]
		td[0] = 1
		for i in range(1, n):
			s1 += S[i]
			td[i] = min(td[i], td[i - 1] + 1)
			s2 = S[i + 1:i * 2 + 1 + 1]
			if s1 == s2:
				td[i * 2 + 1] = min(td[i] + 1, td[i * 2 + 1])
		return td[n - 1]


class Solution:

	def minSteps(self, string):
		n = len(string)
		dp = [0] * (n + 1)
		for i in range(1, n + 1):
			dp[i] = dp[i - 1] + 1
			if i % 2 == 0 and string[:i // 2] == string[i // 2:i]:
				dp[i] = min(dp[i], dp[i // 2] + 1)
		return dp[-1]


class Solution:

	def minSteps(self, s):
		n = len(s)
		dp = [float('inf')] * n
		dp[0] = 1
		s1 = s[0]
		s2 = ''
		for i in range(1, n):
			s1 += s[i]
			dp[i] = min(dp[i - 1] + 1, dp[i])
			s2 = s[i + 1:i + 1 + i + 1]
			if s1 == s2:
				dp[i * 2 + 1] = min(dp[i * 2 + 1], dp[i] + 1)
		return dp[n - 1]


class Solution:

	def minSteps(self, s):
		n = len(s)
		dp = [0] * (n + 1)
		dp[1] = 1
		for i in range(2, n + 1):
			m = dp[i - 1] + 1
			for j in range(1, i // 2 + 1):
				if s[:j] * 2 == s[:2 * j]:
					m = min(m, dp[j] + 1 + i - 2 * j)
			dp[i] = m
		return dp[-1]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.minSteps(s)
		print(answer)


class Solution:

	def minSteps(self, S):
		dp = [0 for i in range(len(S))]
		i = 1
		dp[0] = 1
		while i < len(S):
			if i % 2 == 0:
				dp[i] = dp[i - 1] + 1
			elif S[i] == S[i // 2]:
				x = i
				y = i // 2
				f = 0
				while y >= 0:
					if S[x] != S[y]:
						dp[i] = dp[i - 1] + 1
						f = 1
						break
					x -= 1
					y -= 1
				if f == 0:
					dp[i] = dp[i // 2] + 1
			else:
				dp[i] = dp[i - 1] + 1
			i += 1
		return dp[len(S) - 1]


class Solution:

	def minSteps(self, S):
		n = len(S)
		dp = [100000 for i in range(n)]
		s1 = ''
		s2 = ''
		dp[0] = 1
		s1 += S[0]
		for i in range(1, n):
			s1 += S[i]
			s2 = S[i + 1:2 * i + 2]
			dp[i] = min(dp[i], dp[i - 1] + 1)
			if s2 == s1:
				dp[2 * i + 1] = min(dp[i] + 1, dp[2 * i + 1])
		return dp[n - 1]


class Solution:

	def recur(self, s):
		if not s:
			return 0
		if len(s) % 2 == 0:
			if s[:len(s) // 2] == s[len(s) // 2:]:
				return 1 + self.recur(s[:len(s) // 2])
		return 1 + self.recur(s[:-1])

	def minSteps(self, S):
		return self.recur(S)


class Solution:

	def minSteps(self, S):
		n = len(S)
		dp = {}

		def helper(indx, t):
			if (indx, t) in dp:
				return dp[indx, t]
			if indx >= n:
				return 0
			multiply = float('inf')
			add = 1 + helper(indx + 1, t + S[indx])
			if indx + len(t) - 1 < n and S[indx:indx + len(t)] == t:
				multiply = 1 + helper(indx + len(t), t + t)
			dp[indx, t] = min(multiply, add)
			return dp[indx, t]
		return 1 + helper(1, S[0])


class Solution:

	def final(self, s, n):
		if n <= 1:
			return n
		elif n % 2 == 1:
			return 1 + self.final(s, n - 1)
		elif s[0:n // 2] == s[n // 2:n]:
			return 1 + self.final(s, n // 2)
		else:
			return 1 + self.final(s, n - 1)

	def minSteps(self, S):
		return self.final(S, len(S))


class Solution:

	def minSteps(self, S):
		dp = [0 for i in range(len(S) + 1)]
		for i in range(1, len(S) + 1):
			if i % 2 == 0:
				if S[:i // 2] == S[i // 2:i]:
					dp[i] = dp[i // 2] + 1
				else:
					dp[i] = dp[i - 1] + 1
			else:
				dp[i] = dp[i - 1] + 1
		return dp[len(S)]


class Solution:

	def minSteps(self, S):
		d = {}
		s = self.get(S, 0, d)
		return s

	def get(self, s, i, d):
		if i >= len(s):
			return 0
		elif i == 0:
			d[i] = 1 + self.get(s, i + 1, d)
		elif i in d:
			return d[i]
		else:
			j = 0
			k = i
			while j < i and k < len(s) and (s[j] == s[k]):
				k += 1
				j += 1
			if j == i:
				d[i] = min(1 + self.get(s, k, d), 1 + self.get(s, i + 1, d))
			else:
				d[i] = 1 + self.get(s, i + 1, d)
		return d[i]


class Solution:

	def minSteps(self, S):
		s = S
		dp = [len(s) for x in range(len(s))]
		s1 = ''
		s2 = ''
		s1 = s1 + s[0]
		dp[0] = 1
		for i in range(1, len(s)):
			s1 = s1 + s[i]
			s2 = s[i + 1:i + 1 + i + 1]
			dp[i] = min(dp[i], dp[i - 1] + 1)
			if s1 == s2:
				dp[2 * i + 1] = min(dp[i] + 1, dp[2 * i + 1])
		return dp[len(s) - 1]


class Solution:

	def minSteps(self, S):
		c = 0
		s = S
		while len(s):
			if len(s) % 2 != 0:
				c += 1
				s = s[0:len(s) - 1]
			else:
				t = len(s) // 2
				if s[0:t] == s[t:]:
					s = s[0:t]
					c += 1
				else:
					s = s[0:len(s) - 1]
					c += 1
		return c


class Solution:

	def minSteps(self, S):
		n = len(S)
		count = 0
		temp = S
		while temp:
			if temp[:n // 2] == temp[n // 2:]:
				temp = temp[:n // 2]
				n -= n // 2
			else:
				temp = temp[:-1]
				n -= 1
			count += 1
		return count


class Solution:

	def minSteps(self, S):
		if len(S) == 1:
			return 1
		list1 = []
		list1.append(1)
		for i in range(1, len(S)):
			if (i + 1) % 2 == 0 and S[0:i // 2 + 1] == S[i // 2 + 1:i + 1]:
				list1.append(min(list1[i - 1] + 1, list1[i // 2] + 1))
			else:
				list1.append(list1[i - 1] + 1)
		return list1[len(S) - 1]