Next Permutation From Pool - Facebook Top Interview Questions


Problem Statement :


You are given two strings digits and lower both representing decimal numbers. 

Given that you can rearrange digits in any order, return the smallest number that's larger than lower. You can assume there is a solution.

Constraints

1 ≤ n ≤ 100,000 where n is the length of digits

1 ≤ m ≤ 100,000 where m is the length of lower

Example 1

Input

digits = "852"

lower = "100"

Output

"258"

Example 2

Input

digits = "090"

lower = "0"

Output

"9"

Explanation

We can have "009".



Solution :



                        Solution in C++ :

string solve(string digits, string lower) {
    lower = string(digits.size() - lower.size(), '0') + lower;
    int c[128] = {0};
    for (auto d : digits) ++c[d];
    int n = digits.size();
    string ret(n, '.');
    int m = 0;
    while (m < n && c[lower[m]] > 0) --c[lower[m]], ret[m] = lower[m], ++m;

    auto make = [&](int x) {
        if (x >= lower.size()) return false;
        for (int d = lower[x] + 1; d <= '9'; ++d)
            if (c[d] > 0) {
                ret[x++] = d;
                --c[d];
                for (char y = '0'; y <= '9'; ++y)
                    while (c[y]-- > 0) ret[x++] = y;
                return true;
            }
        return false;
    };

    while (m >= 0 && !make(m)) --m, ++c[lower[m]];
    int b = 0;
    while (b < ret.size() - 1 && ret[b] == '0') ++b;
    return ret.substr(b);
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    // remove prefix 0 of a string. "0005040" returns "5040"
    private String removePrefix0(String str) {
        for (int i = 0; i != str.length(); i++)
            if (str.charAt(i) != '0')
                return str.substring(i, str.length());
        return "0";
    }

    private int[] count(String str) {
        int[] res = new int[10];
        for (int i = 0; i != str.length(); i++) res[str.charAt(i) - '0']++;
        return res;
    }

    // given digit count, sum up the digits from 0 to 9
    private int sumOfDigit0to9(int[] count) {
        int sum = 0;
        for (int v : count) sum += v;
        return sum;
    }

    // given digit count, sum up the digits from 1 to 9
    private int sumOfDigit1to9(int[] count) {
        int sum = 0;
        for (int i = 1; i != 10; i++) sum += count[i];
        return sum;
    }

    // function to tell if we have any digit in our supply that larger than wanted digit
    private boolean hasLarge(int[] supply, int want) {
        for (int i = want + 1; i != 10; i++)
            if (supply[i] != 0)
                return true;
        return false;
    }

    // find the last position that we can beat the lower
    // aware of the non-zero digits that I must consume
    private int getLastBeat(int[] raw, String lower) {
        int[] supply = raw.clone();
        int last = -1;
        int solid = sumOfDigit1to9(supply);
        for (int i = 0; i != lower.length(); i++) {
            final int want = lower.charAt(i) - '0';

            // if at this time the rest of supplied digit can beat this digit of lower, record it
            if (hasLarge(supply, want))
                last = i;

            final boolean cansame;
            if (want == 0) // if want 0, but I have a lot of non-zero digits, we can't be the same
                cansame = (solid < lower.length() - i && supply[0] != 0);
            else // if not 0, simply find out if we can supply this digit
                cansame = supply[want] != 0;

            // try to be the same
            if (cansame == false)
                break;

            // otherwise, we can greedily be the same
            supply[want]--;
            if (want != 0)
                solid--;
        }
        return last;
    }

    private String getSolidString(int[] supply) {
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i != 10; i++)
            for (int c = supply[i]; c != 0; c--) sb.append(i);
        return sb.toString();
    }

    public String solve(String digits, String lower) {
        lower = removePrefix0(lower);
        {
            int[] countSupply = count(digits);
            int[] countDemand = count(lower);
            // nonzerosupplytotal > demandtotal
            if (sumOfDigit1to9(countSupply) > sumOfDigit0to9(countDemand)) {
                StringBuilder sb = new StringBuilder();
                for (int i = 1; i != 10; i++)
                    for (int c = countSupply[i]; c != 0; c--) sb.append(i);
                return sb.toString();
            }
        }

        int[] supply = count(digits);
        final int last = getLastBeat(supply, lower);
        StringBuilder sb = new StringBuilder(digits.length());
        if (last == -1) { // get the least non-zero as the digit, then fill 0
            String solid = getSolidString(supply); // if digits == 5004, would get 45
            sb.append(solid.charAt(0)); // use the first digit
            for (int zeroes = lower.length() - (solid.length() - 1); zeroes != 0;
                 zeroes--) // fill 0
                sb.append(0);
            sb.append(solid.substring(1)); // use the rest digits
        } else {
            // otherwise, we have a position that we can beat lower

            // before that position, we try to maintain the same
            for (int i = 0; i != last; i++) {
                int dig = lower.charAt(i) - '0';
                sb.append(dig);
                supply[dig]--;
            }

            // at that position, find a remaining digit that we can beat the target digit
            for (int i = lower.charAt(last) - '0' + 1; i != 10; i++) {
                if (supply[i] != 0) {
                    sb.append(i);
                    supply[i]--;
                    break;
                }
            }

            // fill 0 if we have to
            for (int c = lower.length() - sb.length() - sumOfDigit1to9(supply); c != 0; c--)
                sb.append(0);

            // put in the rest digits in order
            for (int i = 1; i != 10; i++)
                for (int c = supply[i]; c != 0; c--) sb.append(i);
        }
        return sb.toString();
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, digits, lower):
        added = len(digits) - len(lower)
        digitfreq = defaultdict(int)
        for x in digits:
            digitfreq[int(x)] += 1
        if added:
            lower = ("0" * added) + lower
        l = []
        assert self.dfs(l, digitfreq, lower, False)

        # handle leading zeroes
        l = l[::-1]
        while l and l[-1] == "0":
            l.pop()
        l = l[::-1]
        return "".join(l)

    def dfs(self, l, digitfreq, lower, is_bigger):
        if is_bigger:
            # our current number is definitely bigger, so just append the rest in sorted order
            for v in range(10):
                while digitfreq[v]:
                    digitfreq[v] -= 1
                    l.append(str(v))
            return True
        if len(l) == len(lower):
            # we actually exactly generated the desired number, which is unacceptable
            return False
        x = int(lower[len(l)])
        if digitfreq[x]:
            # try to append the next digit in `lower`
            l.append(str(x))
            digitfreq[x] -= 1
            if self.dfs(l, digitfreq, lower, False):
                return True
            digitfreq[x] += 1
            l.pop()
        x += 1
        # try to append a larger digit
        while x < 10:
            if digitfreq[x]:
                l.append(str(x))
                digitfreq[x] -= 1
                assert self.dfs(l, digitfreq, lower, True)
                return True
            x += 1
        return False
                    

View More Similar Problems

Insert a Node at the Tail of a Linked List

You are given the pointer to the head node of a linked list and an integer to add to the list. Create a new node with the given integer. Insert this node at the tail of the linked list and return the head node of the linked list formed after inserting this new node. The given head pointer may be null, meaning that the initial list is empty. Input Format: You have to complete the SinglyLink

View Solution →

Insert a Node at the head of a Linked List

Given a pointer to the head of a linked list, insert a new node before the head. The next value in the new node should point to head and the data value should be replaced with a given value. Return a reference to the new head of the list. The head pointer given may be null meaning that the initial list is empty. Function Description: Complete the function insertNodeAtHead in the editor below

View Solution →

Insert a node at a specific position in a linked list

Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e

View Solution →

Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

View Solution →

Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing

View Solution →

Reverse a linked list

Given the pointer to the head node of a linked list, change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty. Example: head references the list 1->2->3->Null. Manipulate the next pointers of each node in place and return head, now referencing the head of the list 3->2->1->Null. Function Descriptio

View Solution →