牛牛与字符串3题解

牛牛有一个环形字符串s，牛牛想找到与该字符串循环同构所有字符串中字典序最小的起始位置。

题解：循环同构的意思为 假如有一个字符串为"abc" 那么它所有的循环同构字符串为 "abc" "bac" "cab"
我们可以维护两个指针i,j，所以当 s[i]==s[j]时就有 k++；当 s[i]>s[j]时 就说明 以i开头的字符串不能可能是最小表示 则 i=i+k+1；反之则 j=j+k+1；
时间复杂度：O(n)
空间复杂度：O(1)
参考代码如下：

class Solution {
public:
    /**
     * 返回与该字符串循环同构所有字符串中字典序最小的起始位置
     * @param s string字符串 代表题意中的s
     * @return int整型
     */
    int solve(string s) {
        // write code here
        int n = s.size();
        int i = 0, j = 1, k = 0, t;

        while (i < n && j < n && k < n)
        {
            t = s[(i + k) % n] - s[(j + k) % n];

            if (!t)
                k++; 
            else
            {
                if (t > 0)
                    i += k + 1;
                else
                    j += k + 1; 
                if (i == j)
                    j++;
                k = 0;
            }
        }
        return (i > j ? j : i) + 1;
    }
};