Waste less time on Facebook — follow Brilliant.

Not so trivial, is it?

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.

Note by Sharky Kesa
1 year, 5 months ago

No vote yet
1 vote


Sort by:

Top Newest

Got an entry on OEIS. The formula there says 672. Ivan Koswara · 1 year, 5 months ago

Log in to reply

@Ivan Koswara Damn, that looks neat. Anyone got a proof for that? The best I got was 674. Sharky Kesa · 1 year, 5 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...