I got an idea of this problem.
First we reverse this string, then we use dp to find the LCS of these two strings. Using dp will take O(2n) space, but will use O(n^2) time. TLE! Is there anybody to help me? Thanks!
I got an idea of this problem.
First we reverse this string, then we use dp to find the LCS of these two strings. Using dp will take O(2n) space, but will use O(n^2) time. TLE! Is there anybody to help me? Thanks!
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3857 |
| 2 | jiangly | 3810 |
| 3 | maroonrk | 3534 |
| 4 | tourist | 3528 |
| 5 | Kevin114514 | 3510 |
| 6 | turmax | 3411 |
| 7 | Um_nik | 3387 |
| 8 | Radewoosh | 3367 |
| 9 | heuristica | 3322 |
| 10 | strapple | 3317 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | maspy | 150 |
| 3 | Um_nik | 146 |
| 4 | Errichto | 139 |
| 5 | nik_exists | 138 |
| 6 | adamant | 136 |
| 7 | maroonrk | 134 |
| 8 | DNR | 133 |
| 9 | Dominater069 | 131 |
| 9 | AmShZ | 131 |
You can limit n to 2600 (26 lower case Latin letters * maximum required palindrome length 100).
thank you
Use Suffix Automation to approach it.