Given two strings, find the minimum no. of steps required to covert one to the other?

Given a string of n characters, find the longest palindrome in the string.

O(n2) is simple, O(n) is nice

Knapsack Problem Variation

Given infinite supply of "n" denominations of coins and a change amount "A", give an algorithm to use minimum number of coins to do the transaction?