题意理解

当第i个字母小于第i+k个字母时，可以交换两个字母顺序，记作一次交换。我们要求给定的字符串中，最多可以进行几次交换，直到不存在符合交换条件的两个对应字母。

方法一

可以看到，第i、i+k、i+2k、i+3k等等这些字母之间进行交换，和其它字母无关，所以可以把这样的字母序列提取出来，依次计算每一个序列里面的最多交换次数再相加。对于一个序列，我们使用逆序对（小的字母在前视为逆序）的个数作为该序列的最多交换次数。

正确性证明：
1、若一个序列存在逆序对，则必存在相邻两个字母是逆序的。
2、交换这两个相邻的逆序字母，只会减少一个逆序对。
有了以上两点就可以保证序列逆序对的个数是该序列的最多交换次数。

至于如何求逆序对的个数，这里使用了归并排序的思想，序列a[begin]~a[end]的逆序对个数等于序列a[begin]~a[mid]的逆序对个数加序列a[mid+1]~a[end]的逆序对个数，再加上将两者合并时产生的逆序对个数。

具体代码如下：

class Solution {
public:
    /**
     * 
     * @param s string字符串 s.size() <= 1e5
     * @param k int整型 k <= s.size()
     * @return int整型
     */
    vector<char> v;
    //合并两个序列
    int merge(vector<char> &a, int begin, int mid, int end)
    {
        int p = begin, q = mid + 1;
        int count = 0;
        vector<char> temp;
        //先通过比较大小，将大的字母先插入
        while (p<=mid && q<=end)
        {
            if (a[p]>=a[q])
            {
                temp.push_back(a[p++]);
            }
            else
            {
                count += mid - p + 1;//计算a[q]对应逆序对个数
                temp.push_back(a[q++]);
            }
        }
        //将剩余的字母插入
        while (p<=mid) temp.push_back(a[p++]);
        while (q<=end) temp.push_back(a[q++]);
        //更新a[begin]~a[end]
        for (int i=0;i<temp.size();i++)
        {
            a[i+begin] = temp[i];
        }
        return count;
    }
    //求逆序对个数
    int countReversed(vector<char> &a, int begin,int end)
    {  
        if (begin < end)
        {  
            int mid = (begin + end) / 2;
            //递归过程
            return (countReversed(a, begin, mid) +
                countReversed(a, mid + 1, end) + merge(a, begin, mid, end));
        }
        else
        {
            return 0;
        }
    }
    
    int turn(string s, int k) {
        // write code here
        int ans = 0;
        for (int i=0;i<k;i++)
        {
            v.clear();
            //提取出第i,i+k,i+2k等等字母作为一个序列
            for (int j=i;j<s.length();j+=k)
            {
                v.push_back(s[j]);
            }
            ans += countReversed(v, 0, v.size()-1);
        }
        return ans;
    }
};

时间复杂度：$O\left(NlogN\right)O(NlogN)$O(NlogN)。求逆序对用到的归并思想，其复杂度为$O\left(\frac{N}{k}log\frac{N}{k}\right)O(\backslash frac\{N\}\{k\}log\backslash frac\{N\}\{k\})$O(kN​logkN​)。尽管主程序中有一个双重for循环，内层循环对countReversed函数的调用次数无影响，外层循环控制的该函数执行次数为k次，所以总的时间复杂度为$O\left(NlogN\right)O(NlogN)$O(NlogN)。
空间复杂度：$O\left(N\right)O(N)$O(N)。创建了数组v记录抽取的序列和数组temp记录合并时排好序的新数组。

方法二

同方法一，我们先按照间隔k提取出字符串v，分别进行处理。要求每一个字母前面有多少个小于它的字母。转换一下思路，我们可以求小于它的字母有多少在它前面。

示意图如下：

我们在v上从前向后遍历，如果一个字母出现了，就是用count数组记录，对应count加1,。当遍历到v[j]的时候，v[0]~v[j-1]对应的count都进行了计数，如果没出现的字母其对应count为0。此时遍历小于v[j]的字母，将其对应count值加入到最终答案ans中去。

具体代码如下：

class Solution {
public:
    /**
     * 
     * @param s string字符串 s.size() <= 1e5
     * @param k int整型 k <= s.size()
     * @return int整型
     */
    vector<char> v;
    
    
    int turn(string s, int k) {
        // write code here
        int ans = 0;
        for (int i=0;i<k;i++)
        {
            int count[26] = {0};
            v.clear();
            count[s[i]-'a'] = 1;
            //提取字符串v
            for (int j=i;j<s.length();j+=k)
            {
                v.push_back(s[j]);
            }
            for (int j=1;j<v.size();j++)
            {
                //查看小于v[j]的字母中有几个在它前面
                for (int h=0;h<v[j]-'a';h++)
                {
                    ans += count[h];
                }
                count[v[j]-'a']++;
            }
        }
        return ans;
    }
};

时间复杂度：$O\left(N\right)O(N)$O(N)。一共有三重循环，但是s中的每个字母只遍历了一遍；最内层的循环每次至多遍历25个字母，为常数项。
空间复杂度：$O\left(N\right)O(N)$O(N)。创建了数组v记录抽取的序列，数组count长度为常数。