Havannah = Hannah

The answer is merely the length of the string because its a palindrome. For anyone interested in the general problem, below is my code for finding the longest palindrome for any string . The recurrence relationship is memoized. I would love to see full blown DP solutions.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def LP( L , a , b  , Memo = {}):
        #Simple Recurrence relationsip, with memoization
        Key = (a,b)
        if Key in Memo:
                return Memo[Key]
        if b - a < 0:
                Memo[Key] = ''
                return ''
        if b - a == 0:
                Memo[Key] = L[a]
                return L[a]
        if L[a] == L[b]:
                Memo[Key] = L[a] + LP( L , a + 1 , b - 1 , Memo) + L[b]
                return Memo[Key]
        Memo[Key] = max(  LP( L , a + 1 , b , Memo) , LP( L , a , b - 1 , Memo) , key = len )
        return Memo[Key]

def longestPal( L ):
    return LP( L , 0 , len(L) - 1)

The answer is $\boxed{203}$ . The test string is a complete palindrome; not exactly the best testcase to see if the method is correct! Anyway, here is my code, using Dynamic Programming. (The string to be analyzed is in 'str'.)

    final int N = str.length();

    int pl[][] = new int[N][N];

    for (int i = 0; i < N; i++) pl[i][i] = 1;

    for (int L = 2; L <= N; L++)
        for (int i = 0, j = L-1; j < N; i++, j++) {
            if (str.charAt(i) == str.charAt(j)) 
                pl[i][j] = 2+(L > 2 ? pl[i+1][j-1] : 0);
            else
                pl[i][j] = Math.max(pl[i][j-1],pl[i+1][j]);
        }

    out.println(pl[0][N-1]);

Explanation: The table pl[i][j] keeps track of the longest palindrome from position i to j (inclusive). Initially, we set all pl[i][i] = 1, because strings of one character are trivially palindromes.

Now we consider successively substrings of length 2, 3, 4, and so on. Palindrome "growth" happens if this substring has the same character at the beginning and at the end. In that case, we add the two characters to the longest palindrome of the middle section. Otherwise, we copy information about the longest palindrome from the two sections of length L-1 (pick the longest).

This solution is solution in python 3.4

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

watermark = 0
def lenpal(str0, depth):
    global watermark
    res = 0  
    if len(str0) < 2 :
        res = len(str0)
    elif len(str0) == 2 :
        res = 2 if str0[0] == str0[1] else 1
    else:       
        for i in range(len(str0)-1):
            for j in range(len(str0) -1 ,i+1, - 1):
                if str0[i] == str0[j] and 2*depth + j -i > watermark:
                    res = max(res, 2 + lenpal(str0[i+1:j], depth + 1))
    watermark = max(watermark, res + 2*depth)
    return res

thestr ='79776995125591966288822764239979864294919636529599153749317118101911111012111163616102113319219811581118511891291331120161636111121011111910181171394735199592563691949246897993246722888266919552159967797'

print(lenpal(thestr, 0))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

>>> import itertools
>>> def g(n,k):
    N = str(n)
    K = []
    W = []
    for j in itertools.combinations(N,k):
        B = ''
        for t in j:
            B += t
        K.append(str(B))
    for k in K:
        a = list(k)
        if (a[::-1]==a):
            W.append(k)
    return W
>>> def t(n):
    y = len(str(n))
    while g(n,y)== []: \\as the longest length can be just the length of the string 
        y -=1
        return y

Really nice troll!

Code worked for all my tests, but it still might be a bit buggy.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

final static String n = "..."; //the number in the file
public static void main(String args[]){
    int max = 0;
    if(pal(n))
        max = n.length();
    for(int i = 1; i < n.length(); i++)
        for(int x = 0; x < i; x++)
            if(pal(remove(x,i)) && remove(x,i).length() > max)
                    max = remove(x,i).length();
    System.out.println(max);
}

private static boolean pal(String str) {
    return str.equals(new StringBuilder(str).reverse().toString());
}

private static String remove(int start, int end){
    return n.replace(n.substring(start, end), "");
}

I added a palindrome check for the original string at the start of the program just to be sure and then I realized that I am trolled.

Anyways, nice troll.