Perfect Team Lineups

Problem Statement

Perfect Team Lineups Problem Description In a sports league every player is assigned a rank , an integer from 1 to k. A lineup is a sequence of n players, so it is an array of n integers, each between 1 and k. There are exactly k^n different lineups. A team is a block of k consecutive players in the lineup, that is, a contiguous subarray of length exactly k. A team is perfect if it contains every rank from 1 to k exactly once, i.e. the k players in that block are a permutation of 1, 2, ..., k. The cost of a lineup is the maximum number of perfect teams that can be selected from it so that no two selected teams share a player. A player belongs to at most one selected team, and the cost is the size of the largest such selection, not the number of perfect blocks the lineup happens to contain. For example, with k = 3 and the lineup [1, 2, 1, 3, 2, 3, 2, 1, 3] of length n = 9, the cost is 2: the block from player 2 to player 4 and the block from player 7 to player 9 are both perfect and sha