Solution For Construct Smallest Number From Di String

Problem Statement:

Given a string s that represents a permutation of digits from 0 to 9 inclusive, we need to construct the smallest possible number from this string such that the number is a valid integer (leading zeros are allowed) and follows the pattern given by “D” and “I” characters in the string.

Example:

Input: “DIDIDDIID”
Output: “1492607538”
Explanation:
Each “D” indicates that the next number should be smaller than the previous number, and each “I” indicates that the next number should be larger than the previous number. So, starting with 9 (the largest number), the next number should be smaller (i.e., 8), and so on, until we reach 1. Then, the next number should be larger (i.e., 4), and so on, until we reach 8. Finally, we append 0, the only remaining digit, to the end of the string to obtain the desired output.

Solution:

To construct the smallest possible number from the given string s, we can use a greedy approach. We start with the largest digit 9 and the smallest digit 0, and maintain two pointers i and j, pointing to the current position in the string s and the next available digit in the output string res, respectively.

We traverse the string s character by character, and whenever we encounter a “D” character in s, we append the current smallest digit j to the output string res and increment j by 1. Similarly, whenever we encounter an “I” character in s, we append the current largest digit i to the output string res and increment i by 1.

After traversing the entire string s, we simply append the remaining digits in the range i to 9 (inclusive) or j to 0 (inclusive) to the output string res, depending on whether the last character in s was “I” or “D”, respectively. This ensures that the output string res is a valid integer and follows the pattern specified by the input string s.

Time Complexity:

The time complexity of this approach is O(n), where n is the length of the input string s.

Space Complexity:

The space complexity of this approach is O(n), where n is the length of the input string s (for storing the output string res).

Step by Step Implementation For Construct Smallest Number From Di String

class Solution {
    public String smallestFromDigits(String s) {
        int n = s.length();
        int[] arr = new int[n];
        for(int i=0; i
def smallest_number(s): 

n = len(s) 

# Base case 

if n == 0: 

return "" 

if n == 1: 

return s 

# Sort the string in increasing order of 

# characters 

s = sorted(s) 

# We consider two cases, the first 

# character is 'I' or 'D' 

# If the first character is 'I', we find 

# the smallest number with same set of 

# characters by recursively calling 

# the same function 

if s[0] == 'I': 

return s[0] + smallest_number(s[1:]) 

# If the first character is 'D', we find 

# the smallest number with same set of 

# characters by recursively calling 

# the same function 

else: 

return s[-1] + smallest_number(s[:-1])
var construct = function(S) {
    let res = "";
    let low = 0;
    let high = S.length - 1;
    
    while (low <= high) {
        let left = false;
        let right = false;
        
        for (let i = low; i <= high; i++) {
            if (S.charAt(i) === 'I') {
                left = true;
                break;
            }
        }
        
        for (let j = high; j >= low; j--) {
            if (S.charAt(j) === 'D') {
                right = true;
                break;
            }
        }
        
        if (left) {
            res += low;
            low++;
        }
        
        if (right) {
            res += high;
            high--;
        }
    }
    
    return res;
};
class Solution {
public:
    string smallestFromDigits(string s, int n) {
        string res = "";
        for (int i = 0; i < n; ++i) {
            int idx = 0;
            for (int j = 1; j < s.size(); ++j) {
                if (s[j] < s[idx]) {
                    idx = j;
                }
            }
            res += s[idx];
            s.erase(s.begin() + idx);
        }
        return res;
    }
};
public class Solution {
    public string SmallestFromDigits(string s)
    {
        // Create a list of integers from the input string
        List nums = new List();
        foreach (char c in s)
        {
            nums.Add(c - '0');
        }
        
        // Sort the list in ascending order
        nums.Sort();
        
        // Use a StringBuilder to construct the smallest number
        StringBuilder sb = new StringBuilder();
        foreach (int n in nums)
        {
            sb.Append(n);
        }
        
        return sb.ToString();
    }
}