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

Difficulty: interview

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
            #print(left, right)
            while(left + length <= right - length+1 ):
                #print(text[left:left+length],text[right-length+1:right+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
            # if st1 == mx: return True
            return False
        
        if len(text) == 1: return 1
        ln = len(text)
        # dp = [(1,-1)]*((ln>>1)+1)
        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 = dp[i-1][1] + 1
            st1 = b[1] + 1
            # rnd = random.randint(3,1000)
            hsh_st += ord(text[i-1])
            st2 = ln - i
            hsh_ed += ord(text[st2])
            total = st1 + ln_ch
            # print(f'cmp - {text[st1:total]} {text[st2:st2+ln_ch]}')
            # print(f'st - {st1}, {st2}, {total}')
            res = False
            if hsh_st == hsh_ed:
                # res = True
                res = check_eq(text,st1,st2,total)
            if res:
                # print(f'--True--')
                # dp[i] = (dp[i-1][0]+2,i-1)
                b,a = (b[0]+2,i-1) ,b
                # a = b
                ln_ch = 0
                hsh_st = 0
                hsh_ed = 0
            else:
                # dp[i] = dp[i-1]
                b,a = b,b
        # print(dp)
        # print(b,a)
        if b[0] > a[0] and b[0] > 1 and len(text)%2 == 0:
            return b[0] -1
        return b[0]
        
        # if dp[-1][0] > dp[-2][0] and dp[-1][0] > 1 and len(text)%2 == 0:
            # return dp[-1][0] - 1
        # return dp[-1][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]):
                    #print(i,j,k,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)