For any valid partition, since each part consists of an even number of the same characters, we can further partition each part into lengths of exactly <code>2</code>.

After noticing the first hint, we can decompose the whole string into disjoint blocks of size <code>2</code> and find the minimum number of changes required to make those blocks beautiful.