题目描述

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。

请定义一个函数实现字符串左旋转操作的功能。

比如输入字符串”abcdefg”和数字 2，该函数将返回左旋转 2 位得到的结果”cdefgab”。

注意：

• 数据保证 n 小于等于输入字符串的长度。

样例

输入："abcdefg" , n=2

输出："cdefgab"

算法

(字符串翻转) $O(n)$

曲线救国，直接做不好做，分两步操作

1. 翻转整个字符串
2. 先翻转前一半字符串（未左旋部分）
3. 再翻转后一半字符串（左旋部分）

时间复杂度

字符串翻转时间复杂度 $O(n)$，额外空间复杂度 $O(1)$，最优解法

C++ 代码

class Solution {
public:
    string leftRotateString(string str, int n) {
        reverse(str.begin(), str.end());
        reverse(str.begin(), str.begin() + str.size() - n);
        reverse(str.begin() + str.size() - n, str.end());
        return str;
    }
};