SPOILERS BELOW:

Active In

Competitive Programming

International Olympiad in Informatics

Indian Computing Olympiad (ICO)

Stand-up Comedy

USA Computing Olympiad

Algorithms and Data Structures

Sphere Online Judge (SPOJ)

Quotes

TED Talks

ACM International Collegiate Programming Contest

Featured Contributions

reply in this discussion

reply in this discussion

This problem can be solved with row swapping . Let's discuss the observation.

O(n^2) solution is like as below:

dp[ i ][ j ] = dp[ i + 1 ][ j - 1] ( if s[i] = s[j] )

dp[ i ][ j ] = min( dp[ i +1 ][ j ] + 1 , dp[ i ][ j - 1]+1 ) ( if s[i] != s[j] )

for any row i we just need the information from the next row i+1. The i+2 ,i+3 , i+4 ........ rows are not in use anymore . For that reason at any moment we'll keep the info of two rows i and i+1 . and we can store these information in a table dp[ 2 ][ n ] . the solution has O(n) complexity .

Read more… (133 words)