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
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:
        
        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
