I found this problem quite interesting.

Sharky has a word of 2015 letters made of S and K letters only (e.g. SKSSS, KSKSK). A **palindrome** is a word which can be read the same as looking from left to right or right to left.

Sharky decides to cut up his word into sub-words such that each sub-word is a palindrome. Given that each sub-word must contain a natural number of letters (No cutting up a letter in half), find the minimum number of sub-words that can be cut out for any word of Sharky's.

## Comments

Sort by:

TopNewestGot an entry on OEIS. The formula there says 672. – Ivan Koswara · 7 months, 2 weeks ago

Log in to reply

– Sharky Kesa · 7 months, 2 weeks ago

Damn, that looks neat. Anyone got a proof for that? The best I got was 674.Log in to reply