Next Lexicographic Permutation of String

Problem

Given a sequence (string or array) of comparable elements, produce the lexicographically next permutation in-place. If the input is the highest permutation (sorted in descending order), transform it into the lowest permutation (sorted in ascending order) or indicate that no larger permutation exists.

This is the canonical "next permutation" operation used by std::next_permutation and appears as LeetCode 31.

Examples

Example 1

Input: s = "ABCD"
Output: "ABDC"
Explanation: the next lexicographic permutation after "ABCD" is "ABDC".

Example 2

Input: s = "DCBA"
Output: "ABCD"
Explanation: "DCBA" is the highest permutation; wrap to lowest.

Solution

Method 1 - In-place iterative (standard next-permutation)

Intuition

Traverse from right to left to find the first position where the sequence increases (i). Swapping at that pivot with the smallest larger element to its right (j) and reversing the tail produces the next permutation with the minimal increase.

Approach

1. Find the largest index i such that seq[i-1] < seq[i]. If no such index exists the sequence is the highest permutation — reverse it and return.
2. Find the largest index j >= i such that seq[j] > seq[i-1].
3. Swap seq[i-1] and seq[j].
4. Reverse the subarray seq[i..end] (which was previously non-increasing) to obtain the smallest tail.
5. Edge cases:
   • Repeated elements are handled naturally because comparisons are stable.
   • For strings, operate on characters; for arrays, operate on elements.

Code

C++

class Solution {
 public:
    void nextPermutation(std::vector<int>& nums) {
        int n = nums.size();
        int i = n - 1;
        while (i > 0 && nums[i - 1] >= nums[i]) --i;
        if (i <= 0) { std::reverse(nums.begin(), nums.end()); return; }
        int j = n - 1;
        while (nums[j] <= nums[i - 1]) --j;
        std::swap(nums[i - 1], nums[j]);
        std::reverse(nums.begin() + i, nums.end());
    }
};

Go

func NextPermutation(nums []int) {
    n := len(nums)
    i := n - 1
    for i > 0 && nums[i-1] >= nums[i] { i-- }
    if i <= 0 { reverseInts(nums, 0, n-1); return }
    j := n - 1
    for nums[j] <= nums[i-1] { j-- }
    nums[i-1], nums[j] = nums[j], nums[i-1]
    reverseInts(nums, i, n-1)
}

func reverseInts(a []int, l, r int) {
    for l < r { a[l], a[r] = a[r], a[l]; l++; r-- }
}

Java

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 1;
        while (i > 0 && nums[i - 1] >= nums[i]) i--;
        if (i <= 0) { reverse(nums, 0, n - 1); return; }
        int j = n - 1;
        while (nums[j] <= nums[i - 1]) j--;
        int tmp = nums[i - 1]; nums[i - 1] = nums[j]; nums[j] = tmp;
        reverse(nums, i, n - 1);
    }

    private void reverse(int[] a, int l, int r) {
        while (l < r) { int t = a[l]; a[l++] = a[r]; a[r--] = t; }
    }
}

Kotlin

class Solution {
    fun nextPermutation(nums: IntArray) {
        var i = nums.size - 1
        while (i > 0 && nums[i - 1] >= nums[i]) i--
        if (i <= 0) { nums.reverse(); return }
        var j = nums.size - 1
        while (nums[j] <= nums[i - 1]) j--
        val tmp = nums[i - 1]; nums[i - 1] = nums[j]; nums[j] = tmp
        nums.reverse(i, nums.size)
    }
}

Python

class Solution:
    def nextPermutation(self, nums: list[int]) -> None:
        n = len(nums)
        i = n - 1
        while i > 0 and nums[i - 1] >= nums[i]:
            i -= 1
        if i <= 0:
            nums.reverse()
            return
        j = n - 1
        while nums[j] <= nums[i - 1]:
            j -= 1
        nums[i - 1], nums[j] = nums[j], nums[i - 1]
        nums[i:] = reversed(nums[i:])

Rust

impl Solution {
    pub fn next_permutation(nums: &mut Vec<i32>) {
        let n = nums.len();
        let mut i = n as i32 - 1;
        while i > 0 && nums[i as usize - 1] >= nums[i as usize] { i -= 1; }
        if i <= 0 { nums.reverse(); return; }
        let mut j = n - 1;
        while nums[j] <= nums[i as usize - 1] { j -= 1; }
        nums.swap(i as usize - 1, j);
        nums[i as usize..].reverse();
    }
}

TypeScript

class Solution {
    nextPermutation(nums: number[]): void {
        const n = nums.length;
        let i = n - 1;
        while (i > 0 && nums[i - 1] >= nums[i]) i--;
        if (i <= 0) { nums.reverse(); return; }
        let j = n - 1;
        while (nums[j] <= nums[i - 1]) j--;
        [nums[i - 1], nums[j]] = [nums[j], nums[i - 1]];
        let l = i, r = n - 1;
        while (l < r) { [nums[l], nums[r]] = [nums[r], nums[l]]; l++; r--; }
    }
}

Complexity

• ⏰ Time complexity: O(n) — scanning from the end and a single reverse make linear work in the length n.
• 🧺 Space complexity: O(1) — in-place algorithm uses only a few temporaries.