题解 | #牛牛的字符串#

题意整理

给定一个长度为n的字符串和一个整数k。
每一步可以交换下标i与i+k对应的元素，保证交换之后字典序变大。
求最多交换多少步。

方法一（分组+临时计数统计）

1.解题思路

将字符串分为k组，每组的起点分别是0到 $k-1$ 。
然后分别遍历每一组，并用计数数组记录当前元素访问次数。
如果之前有下标小于当前元素的字符出现，则将其出现次数全部加到结果变量。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param s string字符串 s.size() <= 1e5
     * @param k int整型 k <= s.size()
     * @return int整型
     */
    public int turn (String s, int k) {
        int n=s.length();
        int res=0;
        //分为k组
        for(int i=0;i<k;i++){
            //临时计数数组
            int[] cnt=new int[26];
            for(int j=i;j<n;j+=k){
                //当前字符对应下标
                int index=s.charAt(j)-'a';
                for(int id=0;id<index;id++){
                    //如果有小于当前字符的情况，则加上对应次数
                    res+=cnt[id];
                }
                //当前字符计数加一
                cnt[index]++;
            }
        }
        return res;
    }
}

3.复杂度分析

时间复杂度：循环体最多执行 $26*n$ 次，所以最终的时间复杂度为 $O(n)$ 。
空间复杂度：需要额外n个大小为26的计数数组，所以空间复杂度为 $O(n)$ 。

方法二（利用取余分组）

1.解题思路

初始化计数数组，数组第二维表示对应组的元素出现次数。
通过取余运算，隐式地分为k组。
遍历整个字符串，每次记录对应组元素的出现次数。
如果之前有下标小于当前元素的字符出现，则将其出现次数全部加到结果变量。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param s string字符串 s.size() <= 1e5
     * @param k int整型 k <= s.size()
     * @return int整型
     */
    public int turn (String s, int k) {
        int n=s.length();
        int res=0;
        //初始化计数数组
        int[][] cnt=new int[n][26];
        for(int i=0;i<n;i++){
            //当前字符对应下标
            int index=s.charAt(i)-'a';
            //如果同一组中有小于当前字符的情况，则加上对应次数
            for(int j=0;j<index;j++){
                res+=cnt[i%k][j];
            }
            //在对应组将当前字符对应次数加一
            cnt[i%k][index]++;
        }
        return res;
    }
}

3.复杂度分析

时间复杂度：循环体最多执行 $26*n$ 次，所以最终的时间复杂度为 $O(n)$ 。
空间复杂度：需要额外大小为 $26*n$ 的计数数组，所以空间复杂度为 $O(n)$ 。