Problem

You are given a 0-indexed string pattern of length n consisting of the characters 'I' meaning increasing and 'D' meaning decreasing.

A 0-indexed string num of length n + 1 is created using the following conditions:

  • num consists of the digits '1' to '9', where each digit is used at most once.
  • If pattern[i] == 'I', then num[i] < num[i + 1].
  • If pattern[i] == 'D', then num[i] > num[i + 1].

Return the lexicographically smallest possible string num that meets the conditions._

Examples

Example 1:

1
2
3
4
5
6
7

Input: pattern = "IIIDIDDD"
Output: "123549876"
Explanation: At indices 0, 1, 2, and 4 we must have that num[i] < num[i+1].
At indices 3, 5, 6, and 7 we must have that num[i] > num[i+1].
Some possible values of num are "245639871", "135749862", and "123849765".
It can be proven that "123549876" is the smallest possible num that meets the conditions.
Note that "123414321" is not possible because the digit '1' is used more than once.

Example 2:

1
2
3
4
5

Input: pattern = "DDD"
Output: "4321"
Explanation:
Some possible values of num are "9876", "7321", and "8742".
It can be proven that "4321" is the smallest possible num that meets the conditions.

Constraints:

  • 1 <= pattern.length <= 8
  • pattern consists of only the letters 'I' and 'D'.

Solution

Here are the initial observations:

  • The sequence I (Increasing) means the next number should be greater than the current.
  • The sequence D (Decreasing) means the next number should be smaller than the current.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Brute Force

The most naive strategy would be to generate all possible strings of length n + 1 consisting of digits 1 to 9 and then verify which of them satisfies the conditions defined by the pattern. From all valid strings, we would return the smallest one (lexicographically).

Complexity

  • ⏰ Time complexity: O(9^n)
    • For each digit, we have 9 possible choices.
    • With a string length of n + 1, there are as many as 9^(n+1) possible combinations.
  • 🧺 Space complexity: O(n), due to recursion stack.

Method 2 - Using Backtracking

The naive approach involves generating all permutations of the digits {1, 2, ..., 9} of size n + 1, and then checking which permutation satisfies the constraints given by pattern. From these valid permutations, we’d choose the lexicographically smallest one.

Here is the approach:

  1. Generate Permutations:
    • Use recursion to generate all permutations of integers 1 to n + 1 (only use each digit once).
  2. Validate Each Permutation:
    • For a given permutation, traverse the pattern character by character:
      • If the current character is I, check if perm[i] < perm[i+1].
      • If the current character is D, check if perm[i] > perm[i+1].
    • If any of these checks fail, discard this permutation.
  3. Track the Smallest Valid Permutation:
    • Keep track of the lexicographically smallest valid permutation as you process each permutation.
  4. Return the smallest valid permutation at the end.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

class Solution {
    private String smallest = null;

    public String smallestNumber(String pattern) {
        int n = pattern.length();
        boolean[] used = new boolean[n + 2];
        backtrack(new ArrayList<>(), used, pattern, n + 1);
        return smallest;
    }

    private void backtrack(List<Integer> temp, boolean[] used, String pattern, int maxDigits) {
        if (temp.size() == maxDigits) {
            if (isValid(temp, pattern)) {
                String num = convertToString(temp);
                if (smallest == null || num.compareTo(smallest) < 0) {
                    smallest = num;
                }
            }
            return;
        }

        for (int i = 1; i <= maxDigits; i++) {
            if (!used[i]) {
                used[i] = true;
                temp.add(i);
                backtrack(temp, used, pattern, maxDigits);
                temp.remove(temp.size() - 1);
                used[i] = false;
            }
        }
    }

    private boolean isValid(List<Integer> perm, String pattern) {
        for (int i = 0; i < pattern.length(); i++) {
            if (pattern.charAt(i) == 'I' && perm.get(i) >= perm.get(i + 1)) {
                return false;
            }
            if (pattern.charAt(i) == 'D' && perm.get(i) <= perm.get(i + 1)) {
                return false;
            }
        }
        return true;
    }

    private String convertToString(List<Integer> temp) {
        StringBuilder sb = new StringBuilder();
        for (int num : temp) {
            sb.append(num);
        }
        return sb.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        from itertools import permutations
        
        n: int = len(pattern)
        smallest: str = None
        
        def is_valid(perm: tuple[int]) -> bool:
            for i in range(n):
                if pattern[i] == 'I' and perm[i] >= perm[i + 1]:
                    return False
                if pattern[i] == 'D' and perm[i] <= perm[i + 1]:
                    return False
            return True

        # Try all permutations of numbers 1 to n+1
        for perm in permutations(range(1, n + 2)):
            if is_valid(perm):
                num = ''.join(map(str, perm))  # Convert tuple to string
                if smallest is None or num < smallest:
                    smallest = num

        return smallest

Complexity

  • ⏰ Time complexity: O(n! * n)
    • The recursive approach generates all permutations of 1, 2, ..., n + 1.
    • The number of permutations is (n + 1)!.
    • For each permutation, validating it against the pattern takes O(n) time.
    • Total complexity is approximately O((n+1)! * n).
  • 🧺 Space complexity: O(n)

Method 3 - Using Stack

The key idea is:

  • When encountering D, delay placing the digits until the sequence changes to I or we reach the end of the string. This ensures the digits are added in reverse order (largest first) for these decreasing groups.

Here is the approach:

  • Iterate through the pattern while maintaining a stack.
  • Push the current digit from 1 to 9 into the stack.
  • Whenever an I is encountered or we reach the end of the pattern, pop all elements from the stack and append to the result. This ensures the correct order for decreasing groups.
  • Repeat this process until all characters in the pattern are processed.

Code

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

class Solution {
    public String smallestNumber(String pattern) {
        int n = pattern.length();
        StringBuilder ans = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i <= n; i++) {
            stack.push(i + 1); // Push the current number
            // If the pattern is 'I' or we've reached the end, process the stack
            if (i == n || pattern.charAt(i) == 'I') {
                while (!stack.isEmpty()) {
                    ans.append(stack.pop());
                }
            }
        }
        
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        n: int = len(pattern)
        ans: list[str] = []
        stack: list[int] = []

        for i in range(n + 1):
            stack.append(i + 1)  # Push the current number
            # If the pattern is "I" or we've reached the end, process the stack
            if i == n or pattern[i] == 'I':
                while stack:
                    ans.append(str(stack.pop()))

        return ''.join(ans)

Complexity

  • ⏰ Time complexity: O(n), as each digit is pushed and popped from the stack exactly once.
  • 🧺 Space complexity: O(n) for using stack and storing result.