New Network Protocol

Problem Statement

New Network Protocol Problem Description A string s must be transferred using a new network protocol. Before transmission, the string may be split into one or more non-empty contiguous substrings, and each substring is transmitted on its own. Transmission adds extra time in two ways: Matching pairs. Inside one substring, every pair of positions that hold the same character is a matching pair, and each matching pair costs sameTime seconds. Pairs are counted over all positions of the substring, not only neighbouring ones: a substring in which some character occurs k times contains k * (k - 1) / 2 matching pairs for that character. For example, "aaa" contains 3 matching pairs and "abca" contains 1. Partitions. Every split point costs partitionTime seconds. A string split into m substrings therefore pays (m - 1) * partitionTime ; keeping the string whole pays nothing for partitions. The total extra time is the sum of the matching-pair costs of all substrings plus the partition cost. Find t