题目

有一个长度为 的由小写字母组成的字符串 ，还有一个整数 。
在每一步中，可以选择一个位置 并在 和 处交换字符（）并且 ，即交换之后，新形成的字符串应字典序大于旧字符串。
求最多可以交换多少步。

解题思路

将字符串分成 组子串，每组子串由字符串 中下标 模 后相等的字符组成。
对于每个子串，遍历每个字符，计算子串中位于该字符前面，且小于当前字符的字符个数 ，将这些累加计入 ，返回答案。

下面的代码虽然使用了 3 个循环，但时间复杂度是 。
外面两个循环加起来明显是 ，因为遍历了字符串中的每个字符，且没有重复。
最内的循环为 ，而 ，所以为 。

C++代码

class Solution {
public:
    /**
     * 
     * @param s string字符串 s.size() <= 1e5
     * @param k int整型 k <= s.size()
     * @return int整型
     */
    int turn(string s, int k) {
        // write code here
        int ans = 0;
        int n = s.size();
        for(int i=0; i<k; ++i){
            int num[26] = {0};
            num[s[i]-'a'] = 1;
            for(int j=i+k; j<n; j+=k){
                int index = s[j] - 'a';
                for(int t=0; t<index; ++t){
                    ans += num[t];
                }
                ++num[index];
            }
        }
        return ans;
    }
};