Next Permutation From Pool - Facebook Top Interview Questions

                        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