finding the longest palindrome substring within a string, dynammic programming approach ~ O(n^2)

main.m

// problem: find the longest palindrome substring within a string s 
// e.g., if s = "bananas", the longest palindrome substring is "anana"
//
// dynammic solution:
//
// recursion (in words):
// l[i,j] = longest palindrome substring in string s created starting at index i and ending at index j in string s
// l[i,j] could be an empty string if a palindrome is not possible starting at index i and ending at index j
//
// case (1)
// l[i,j] = s[i] + l[i+1,j-1] + s[j], if s[i] == s[j], and l[i+1,j-1] is not an empty string 
// (e.g., s = "racecar", i=0, j=6, s[i]="r", s[j]="r", l[i+1,j-1] = "aceca")
//
// case (2)
// l[i,j] = s[i] + s[j], if s[i] == s[j], and i == j-1
// (e.g., s = "assdf", i=1, j=2, s[i]="s", s[j]="s", l[i,j] = "ss")
//
// case (3)
// l[i,j] = s[i], if i == j
// (e.g., s = "asdf", i=2, j=2, s[i]="d", s[j]="d", l[i,j] = l[i,i] = "d")
//
// case (4)
// otherwise, l[i,j] = "" (empty string)
//
// base cases:
// l[i,i] = s[i]
// l[i,j] = "", if i > j
//

#import <Foundation/Foundation.h>

NSString* stringAtIndex(NSString *s, NSUInteger index)
{
    return [s substringWithRange:NSMakeRange(index, 1)];
}

NSString* palindrome_dp(NSString *s)
{
    NSMutableArray *l = [[NSMutableArray alloc] init];
    NSUInteger n = [s length];
    
    // initialize l as 2D array of empty strings
    for (int i=0; i<n; ++i) {
        [l addObject:[[NSMutableArray alloc] init]];
        for (int j=0; j<n; ++j) {
            [l[i] addObject:@""];
        }
    }
    
    // populate l and keep track of the max length palindrome created
    int maxLength = 1;
    int maxI = 0;
    int maxJ = 0;
    
    // populate the values diagonally
    for (int k=0; k<n; ++k) {
        for (int i=0; i<n-k; ++i) {
            int j = i + k;
            if (i == j) {
                l[i][j] = stringAtIndex(s, i);
            } else if ([stringAtIndex(s, i) isEqualToString:stringAtIndex(s, j)]) {
                if (i == j-1) {
                    NSString *tmp = [NSString stringWithFormat:@"%@%@", stringAtIndex(s, i), stringAtIndex(s, j)];
                    if ([tmp length] >= maxLength) {
                        maxLength = (int)[tmp length];
                        maxI = i;
                        maxJ = j;
                    }
                    l[i][j] = tmp;
                } else if (![l[i+1][j-1] isEqualToString:@""]) {
                    NSString *tmp = [NSString stringWithFormat:@"%@%@%@", stringAtIndex(s, i), l[i+1][j-1], stringAtIndex(s, j)];
                    if ([tmp length] >= maxLength) {
                        maxLength = (int)[tmp length];
                        maxI = i;
                        maxJ = j;
                    }
                    l[i][j] = tmp;
                }
            }
        }
    }
    
    BOOL shouldLogArray = NO;
    if (shouldLogArray) {
        for (int i=0; i<n; ++i) {
            for (int j=0; j<n; ++j) {
                NSLog(@"l[%d][%d]: %@", i, j, l[i][j]);
            }
        }
    }
    return [s substringWithRange:NSMakeRange(maxI, maxJ - maxI + 1)];
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        NSString *s = @"bananas";
        NSString *p = palindrome_dp(s);
        NSLog(@"palindrome: %@", p);
    }
    return 0;
}