What is the time complexity of Lexicographically Smallest Permutation Greater Than Target?

The optimal solution for Lexicographically Smallest Permutation Greater Than Target runs in O(n) time and uses O(1) space. Only a single pass through the string and a fixed-size array for counting (26 letters).

What is the brute force solution for Lexicographically Smallest Permutation Greater Than Target?

The brute force approach for Lexicographically Smallest Permutation Greater Than Target is Brute Force, with O(n!) time complexity and O(n!) space complexity. Generate all permutations of string s and check each one against target. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Lexicographically Smallest Permutation Greater Than Target?

Lexicographically Smallest Permutation Greater Than Target uses the following concepts: Hash Table, String, Greedy, Counting, Enumeration. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Lexicographically Smallest Permutation Greater Than Target?

Explain your thought process clearly. Consider edge cases, like all characters being the same. Practice similar problems to build intuition.

What are common mistakes when solving Lexicographically Smallest Permutation Greater Than Target?

Not considering all characters when constructing the next permutation. Confusing lexicographical comparison with numerical comparison.

#3720

Lexicographically Smallest Permutation Greater Than Target

Medium

Hash TableStringGreedyCountingEnumerationHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n!)	O(n)
Space	O(n!)	O(1)

💡

Intuition

Time O(n)Space O(1)

Use frequency counting and a greedy approach to construct the next permutation directly without generating all permutations.

⚙️

Algorithm

3 steps

1Step 1: Count the frequency of each character in s.
2Step 2: Traverse target and try to construct the next permutation character by character.
3Step 3: If a character can be used that is greater than the current target character, use it and fill the rest with the smallest available characters.

solution.py17 lines

1from collections import Counter
2
3def next_permutation(s, target):
4    count = Counter(s)
5    result = []
6    for char in target:
7        for c in sorted(count.keys()):
8            if c > char and count[c] > 0:
9                result.append(c)
10                count[c] -= 1
11                break
12        else:
13            result.append(char)
14            count[char] -= 1
15    for c in sorted(count.keys()):
16        result.extend([c] * count[c])
17    return ''.join(result) if ''.join(result) > target else ''

ℹ

Complexity note: Only a single pass through the string and a fixed-size array for counting (26 letters).

1Lexicographical order is about comparing character positions.
2Using frequency counts allows for efficient construction of permutations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.