Problem

Given an input of n distinct characters, find a simple formula to determine the number of valid permutations (An) that can be printed by processing the characters through a stack. A valid permutation is one where the output sequence can be generated using stack operations (push and pop).

Examples

Example 1:

1
2
3

Input: 3
Output: 5
Explanation: There are 5 valid permutations for 3 distinct characters, as given by the 3rd Catalan number (C_n).

Example 2:

1
2
3

Input: 4
Output: 14
Explanation: There are 14 valid permutations for 4 distinct characters, as given by the 4th Catalan number (C_n).

Solution

Method 1 - Catalan Number

We have already seen Catalan Numbers, and use its formula: $$ C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!n!} $$

  1. Understanding the Catalan Number:
    • The nth Catalan number provides the count of different ways to correctly match parentheses, or considering stack operations, the number of valid sequences of push and pop operations.
    • It reflects the number of valid permutations of n elements when pushed and popped from a stack without violating the stack order.
  2. Computational Steps:
    • Compute the factorial values required for the Catalan formula.
    • Use the formula to calculate the Catalan number for the given n.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public class Solution {
    public int numStackPermutations(int n) {
        return binomialCoeff(2 * n, n).divide(BigInteger.valueOf(n + 1)).intValue();
    }

    private BigInteger binomialCoeff(int n, int k) {
        BigInteger result = BigInteger.ONE;
        for (int i = 0; i < k; ++i) {
            result = result.multiply(BigInteger.valueOf(n - i));
            result = result.divide(BigInteger.valueOf(i + 1));
        }
        return result;
    }

    // Examples usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.numStackPermutations(3));  // Output: 5
        System.out.println(solution.numStackPermutations(4));  // Output: 14
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def num_stack_permutations(self, n: int) -> int:
        return math.comb(2 * n, n) // (n + 1)

# Examples usage
solution = Solution()
print(solution.num_stack_permutations(3))  # Output: 5
print(solution.num_stack_permutations(4))  # Output: 14

Complexity

  • ⏰ Time complexity:  O(n) because we only traverse the string once.
  • 🧺 Space complexity: O(1) because we only use a constant amount of additional space.