Slice master

Problem Statement

Slice master Problem You and your friends are playing a game called Slice master . You are given a string S of lowercase English letters. You must cut S into one or more parts . The parts are contiguous pieces of S , laid end to end in their original order, and together they use up the whole string. (inferred - the source says only "slice S into parts"; the parts are contiguous substrings of S that concatenate back to S .) The cut is only legal if every letter stays inside a single part . In other words, if a letter occurs anywhere in a part, then every other occurrence of that letter in S must be in that same part. A part of length x is worth x * x points, and your score is the sum over all parts. Print the minimum score you can obtain with a legal cut of S . Note: For example, if one part contains the letters a , m , i , g , o , then none of those five letters may appear in any other part. Cutting S into a single part (the whole string) is always legal, so a legal cut always exists.