GCJ/2008/2/D/main.go

package main

import (
	"fmt"
)

func nextPerm(nums []int) bool {
	n := len(nums)
	if n < 2 {
		return false
	}
	i := n - 2
	for ; 0 <= i && nums[i+1] <= nums[i]; i-- {
	}
	if i == -1 {
		return false
	}
	j := i + 1
	for ; j+1 < n && nums[i] < nums[j+1]; j++ {
	}
	nums[i], nums[j] = nums[j], nums[i]
	for l, r := i+1, n-1; l < r; l, r = l+1, r-1 {
		nums[l], nums[r] = nums[r], nums[l]
	}
	return true
}

func countGroup(s string, perm []int) int {
	n, k := len(s), len(perm)
	prevByte := s[perm[0]]
	cnt := 1
	for offset := 0; offset < n; offset += k {
		i := 0
		if offset == 0 {
			i = 1
		}
		for ; i < k; i++ {
			if s[offset+perm[i]] != prevByte {
				cnt++
			}
			prevByte = s[offset+perm[i]]
		}
	}
	return cnt
}

func main() {
	var N, k int
	fmt.Scan(&N)
	for cid := 0; cid < N; cid++ {
		fmt.Scan(&k)
		var S string
		fmt.Scan(&S)
		perm := make([]int, k)
		for i := range perm {
			perm[i] = i
		}
		minGroup := countGroup(S, perm)
		for nextPerm(perm) {
			groupCnt := countGroup(S, perm)
			if groupCnt < minGroup {
				minGroup = groupCnt
			}
		}
		fmt.Printf("Case #%d: %d\n", cid+1, minGroup)
	}
}