Blog

Introduction:

Ever wondered how computers generate the smallest possible numbers based on certain patterns? The GeeksforGeeks platform throws us into this fascinating challenge: crafting the minimum number following a unique pattern of ‘I’s and ‘D’s. ‘I’ suggests an increase, ‘D’ implies a decrease. In this adventure, we’ll tackle this problem head-on with a Python solution that keeps things snappy and efficient. Ready to explore the world of creating minimum numbers from patterns? Let’s dive in!

Question:

Given a pattern containing only I’s and D’s, where ‘I’ stands for increasing and ‘D’ stands for decreasing, devise an algorithm to print the minimum number following that pattern. The digits from 1 to 9 cannot repeat.

Example 1:

Input:

D

Output:

21

Explanation:
D indicates decreasing, so we choose the minimum number among all possible numbers like 21, 31, 54, 87, etc.

Example 2:

Input:

IIDDD

Output:

126543

Explanation:
1 < 2 < 6 > 5 > 4 > 3
I – I – D – D – D

Your Task:

You are required to implement the function printMinNumberForPattern(S) that takes a string S and returns a string containing the minimum number following the valid pattern.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ Length of String ≤ 8

Answer:(Python)”You have to run in Geeks FOR Geeks“

class Solution:
    def printMinNumberForPattern(self, S):
        result = ""
        stack = []

        for i in range(len(S) + 1):
            stack.append(i + 1)

            if i == len(S) or S[i] == 'I':
                while stack:
                    result += str(stack.pop())

        return result

Explanation:

The algorithm uses a stack to generate the minimum number following the given pattern. It iterates through the pattern and pushes increasing numbers onto the stack. When it encounters ‘I’ or reaches the end of the pattern, it pops the elements from the stack and appends them to the result string.

The algorithm ensures that the output string follows the given pattern and is the minimum possible number. The time complexity is O(N), where N is the length of the input pattern, and the auxiliary space complexity is O(1) since the stack size remains constant.

Example Usage:

# Example usage:
sol = Solution()
print(sol.printMinNumberForPattern("D"))  # Output: "21"
print(sol.printMinNumberForPattern("IIDDD"))  # Output: "126543"

Output Explanation:

1. For the input pattern “D”, the output is “21”, which is the minimum number following the decreasing pattern.
2. For the input pattern “IIDDD”, the output is “126543”, where 1 < 2 < 6 > 5 > 4 > 3, satisfying the given pattern.

The printMinNumberForPattern method is demonstrated with these examples, showcasing its ability to produce the correct and minimum numbers following the specified patterns.

Conclusion:

This algorithm efficiently solves the problem of generating the minimum number based on the given pattern, adhering to the constraints of the problem. By using a stack to manage the increasing sequence, the algorithm ensures correctness and optimality. The time and space complexity are within the expected limits, making it a suitable solution for the specified task.