Return the largest possible k such that there exists a_1, a_2, ..., a_k such that:

Each a_i is a non-empty string;
Their concatenation a_1 + a_2 + ... + a_k is equal to text;
For all 1 <= i <= k,  a_i = a_{k+1 - i}.

 
Example 1:
Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Example 2:
Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".

Example 3:
Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)".

Example 4:
Input: text = "aaa"
Output: 3
Explanation: We can split the string on "(a)(a)(a)".

 
Constraints:

text consists only of lowercase English characters.
1 <= text.length <= 1000

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Amortized analysis

Greedy algorithms

Starter code: class Solution:
    def longestDecomposition(self, text: str) -> int:
        

Solutions:
class Solution:

	def longestDecomposition(self, text: str) -> int:
		n = len(text)
		splits = 0
		(leftstart, leftend) = (0, 0)
		(rightstart, rightend) = (n - 1, n - 1)
		while leftend < rightstart:
			if text[leftstart:leftend + 1] == text[rightstart:rightend + 1]:
				leftstart = leftend + 1
				leftend = leftstart
				rightstart = rightstart - 1
				rightend = rightstart
				splits += 2
			else:
				leftend += 1
				rightstart -= 1
		return splits + 1 if leftstart <= rightend else splits


class Solution:

	def longestDecomposition(self, text: str) -> int:
		count = 0
		i = 0
		while text:
			if text[:i + 1] == text[-(i + 1):]:
				count += 1
				if i + 1 < len(text):
					count += 1
				text = text[i + 1:-(i + 1)]
				i = 0
				continue
			i += 1
		return count


class Solution:

	def longestDecomposition(self, text: str) -> int:
		n = len(text)

		@lru_cache(None)
		def dfs(i, j):
			if i > j:
				return 0
			if i == j:
				return 1
			res = 1
			k = 1
			while i + k <= j - k + 1:
				if text[i:i + k] == text[j - k + 1:j + 1]:
					res = max(res, 2 + dfs(i + k, j - k))
				k += 1
			return res
		return max(dfs(0, n - 1), 1)


class Solution:

	def longestDecomposition(self, text: str) -> int:
		n = len(text)

		@lru_cache(None)
		def dp(left, right):
			if left > right:
				return 0
			if left == right:
				return 1
			maxk = 1
			length = 1
			while left + length <= right - length + 1:
				if text[left:left + length] == text[right - length + 1:right + 1]:
					maxk = max(maxk, dp(left + length, right - length) + 2)
				length += 1
			return maxk
		x = dp(0, n - 1)
		return x


class Solution:

	def longestDecomposition(self, text: str) -> int:
		found = {}

		def search(start, end):
			if start > end:
				return 0
			if (start, end) in found:
				return found[start, end]
			m = 1
			for i in range(1, (end - start + 1) // 2 + 1):
				if text[start:start + i] == text[end + 1 - i:end + 1]:
					m = max(m, 2 + search(start + i, end - i))
			found[start, end] = m
			return m
		return search(0, len(text) - 1)


from collections import deque

class Solution:

	def longestDecomposition(self, text: str) -> int:

		def check(a, b):
			return all([a[i] == b[i] for i in range(len(a))])
		ans = 0
		(l, r) = (deque([]), deque([]))
		for i in range(len(text) // 2):
			l.append(text[i])
			r.appendleft(text[-1 - i])
			if check(l, r):
				ans += 2
				(l, r) = (deque([]), deque([]))
		if len(text) % 2 == 0 and len(l) == len(r) == 0:
			return ans
		else:
			return ans + 1


class Solution:

	def longestDecomposition(self, text: str) -> int:
		if not text:
			return 0
		(i, j, result) = (0, len(text) - 1, 0)
		while i < j:
			if text[:i + 1] == text[j:]:
				return self.longestDecomposition(text[i + 1:j]) + 2
			else:
				(i, j) = (i + 1, j - 1)
		return 1


class Solution:

	def longestDecomposition(self, text: str) -> int:
		idxMap = defaultdict(list)
		for (i, ch) in enumerate(text):
			idxMap[ch].append(i)
		memo = {}

		def recurse(i, j):
			if i == j:
				return 1
			if i > j:
				return 0
			if (i, j) in memo:
				return memo[i, j]
			curMax = 1
			for k in idxMap[text[i]]:
				if k > j or i == k:
					continue
				if text[i:i + j - k + 1] == text[k:j + 1]:
					curMax = max(2 + recurse(i + j - k + 1, k - 1), curMax)
			memo[i, j] = curMax
			return curMax
		return recurse(0, len(text) - 1)


class Solution:

	def longestDecomposition(self, text: str) -> int:
		(l, r, lh, rh, curr_len, modulo, base, res) = (0, len(text) - 1, 0, 0, 0, 32416189573, 26, 0)
		nums = [ord(c) - ord('a') for c in text]
		while l < r:
			lh = (lh * base + nums[l]) % modulo
			rh = (nums[r] * base ** curr_len + rh) % modulo
			curr_len += 1
			if lh == rh and text[l - curr_len + 1:l + 1] == text[r:r + curr_len]:
				res += 2
				lh = rh = curr_len = 0
			l += 1
			r -= 1
		if l == r or curr_len:
			res += 1
		return res


class Solution:
	import random

	def longestDecomposition(self, text: str) -> int:

		def check_eq(s, st1, st2, mx):
			while s[st1] == s[st2]:
				st1 += 1
				st2 += 1
				if st1 == mx:
					return True
			return False
		if len(text) == 1:
			return 1
		ln = len(text)
		a = (1, -1)
		b = (1, -1)
		hsh_st = 0
		hsh_ed = 0
		ln_ch = 0
		for i in range(1, (ln >> 1) + 1):
			ln_ch += 1
			st1 = b[1] + 1
			hsh_st += ord(text[i - 1])
			st2 = ln - i
			hsh_ed += ord(text[st2])
			total = st1 + ln_ch
			res = False
			if hsh_st == hsh_ed:
				res = check_eq(text, st1, st2, total)
			if res:
				(b, a) = ((b[0] + 2, i - 1), b)
				ln_ch = 0
				hsh_st = 0
				hsh_ed = 0
			else:
				(b, a) = (b, b)
		if b[0] > a[0] and b[0] > 1 and (len(text) % 2 == 0):
			return b[0] - 1
		return b[0]


class Solution:

	def longestDecomposition(self, text: str) -> int:

		@lru_cache(None)
		def helper(i, j):
			if i > j:
				return 0
			if i == j:
				return 1
			ans = 1
			tmp = 0
			l = j - i + 1
			for k in range(1, l // 2 + 1):
				if text[i:i + k] == text[j - k + 1:j + 1]:
					tmp = max(tmp, 2 + helper(i + k, j - k))
			return max(tmp, 1)
		return helper(0, len(text) - 1)