Walmart Labs Interview Question
Developer Program EngineersCountry: India
Interview Type: In-Person
One simple idea might be iterate character by character ( of the string ) thinking that they are the centers of a palindrome. Maintain the position and length of the longest palindrome. Basically, expand from the current center ( if considering an even length palindrome then we can use the convention that the left one is the center and we proceed only if the immediate right one is also same ) until its a valid palindrome. Haven't thought much about the performance. Should be def better than naive
O(n^3)
stackoverflow(dot)com/questions/12430604/longest-palindrome-subsequence
- Anonymous March 24, 2013