The problem
Return a pair (count, longest). count is the number of pieces s[a:b] (with a < b) that are palindromes; pieces with the same letters at different places count separately. longest is the longest palindromic piece; if there is a tie, the one that starts earliest.
palindromes("aaa") # (6, "aaa")
palindromes("abba") # (6, "abba")
palindromes("abaxcdc") # (9, "aba")
The string has at least one lower-case letter.
Limits
- Up to 200,000 letters. The big tests have 4 seconds each.
- The count can be about 20 billion; growing each palindrome from its centre is too slow when there are that many.
Builds on STRG-6 Manacher’s palindromes.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
11 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | abacaba | Not run | |
| 2 | A run | Not run | |
| 3 | Even length | Not run | |
| 4 | Nothing longer than a letter | Not run | |
| 5 | One letter | Not run | |
| 6 | A tie | Not run | |
| 7 | Even wins | Not run | |
| 8 | 200,000 of one letter | Not run | |
| 9 | A long alternating string | Not run | |
| 10 | Random letters | Not run | |
| 11 | The Fibonacci word | Not run |