字符串左旋轉算法：O(n) 時間 O(1) 空間的三步反轉法

問題定義

將字符串前 m 個字符移至尾部。例："abcdef" 左旋 2 位 → "cdefab"。要求時間 O(n)、輔助空間 O(1)。

三種思路對比

1. 輔助數組法 —— 空間 O(n) ✗

新建長度 n 數組，前半段放後 n-m 個，後半段放前 m 個。簡單但違反空間約束。

2. 逐位循環移位法 —— 邊界處理複雜 ✗

保存 str[0]，將 str[m] 移到 0，str[2m] 移到 m… 當 n 非 m 倍數時需多輪循環，代碼極易出錯。

3. 三步反轉法 —— 最優解 ✓

將字符串視為 XY，目標變為 YX：

1. 反轉前半段 X → Xᵀ
2. 反轉後半段 Y → Yᵀ
3. 整體反轉 XᵀYᵀ → (XᵀYᵀ)ᵀ = YX

每步原地雙指針交換，總交換次數 n，空間僅需 1 個 char 暫存變量。

完整實現

public static String leftRotate(StringBuilder sb, int m) {
    int n = sb.length();
    if (m < 0 || m > n) throw new IllegalArgumentException("旋轉位數非法");
    if (m == 0 || m == n) return sb.toString();

    reverse(sb, 0, m - 1);       // 步驟 1
    reverse(sb, m, n - 1);       // 步驟 2
    reverse(sb, 0, n - 1);       // 步驟 3
    return sb.toString();
}

private static void reverse(StringBuilder sb, int left, int right) {
    while (left < right) {
        char tmp = sb.charAt(left);
        sb.setCharAt(left, sb.charAt(right));
        sb.setCharAt(right, tmp);
        left++; right--;
    }
}

執行軌跡演示

原始: a b c d e f   (m=2, n=6)
步驟1: b a c d e f   反轉 [0,1]
步驟2: b a f e d c   反轉 [2,5]
步驟3: c d e f a b   反轉 [0,5]  ✓

擴展：右旋轉

右旋 k 等價於左旋 n-k：

public static String rightRotate(StringBuilder sb, int k) {
    int n = sb.length();
    return leftRotate(sb, (n - (k % n)) % n);
}

應用場景

• 環形緩衝區邏輯索引轉換
• 字符串加密/混淆預處理
• 文本編輯器塊移動操作

三步反轉法以數學優雅性滿足嚴格複雜度要求，是字符串原地變換的經典範例。