{x}
blog image

Construct Smallest Number From DI String

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.

 

Example 1:

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:

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 Explanation

This problem asks to construct the lexicographically smallest string num of length n+1 (where n is the length of the input string pattern) that satisfies the conditions specified by the pattern string. The pattern string consists of 'I' (increasing) and 'D' (decreasing) characters, indicating the relationship between adjacent digits in num.

The solution uses a backtracking approach to explore all possible combinations of digits that satisfy the conditions. The backtracking algorithm explores the possible digit choices at each position in num.

Approach:

  1. Initialization: A vis array (or set) is used to keep track of which digits have already been used. A t array (or string builder) stores the digits of the current solution being constructed. ans stores the lexicographically smallest string found so far.

  2. Recursive Depth-First Search (DFS): The dfs(u) function recursively explores the possibilities:

    • Base Case: If u reaches len(pattern) + 1, it means a complete num string has been constructed. We update ans if the new string is lexicographically smaller than the current ans.

    • Recursive Step: The algorithm iterates through digits 1 to 9. If a digit is not already used (!vis[i]):

      • It checks if the current digit satisfies the increasing/decreasing condition specified by the pattern at the current position (u).

      • If the condition is met, it marks the digit as used (vis[i] = True), adds it to the t array, and recursively calls dfs(u + 1) to explore the next position.

      • After the recursive call, it backtracks: it marks the digit as unused (vis[i] = False) and removes it from t to explore other possibilities.

  3. Lexicographical Ordering: The lexicographically smallest string num is found by maintaining the ans variable and updating it whenever a smaller string is found.

Time Complexity Analysis:

The time complexity is dominated by the backtracking search. In the worst case, the algorithm might explore all possible permutations of the digits 1 to 9, which is 9! (9 factorial). However, the constraints limit the length of pattern to 8, so the number of possible num strings is significantly less than 9!. The actual time complexity will depend on the specific input pattern but is bounded by O(9!). However, due to constraints, it is more practical to say it is at most O(9!), but it will generally be much smaller than that.

Space Complexity Analysis:

The space complexity is determined by the recursive call stack and the auxiliary arrays/variables used. The depth of the recursive stack is at most n + 1 (length of num). The space used by the vis array is O(10) (constant). The space used by t is O(n) (linear in the length of pattern). Therefore, the overall space complexity is O(n), where n is the length of the input string. Again, n is limited by the problem constraints, meaning space complexity is effectively O(1) due to constraints.