# 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):
digitfreq = defaultdict(int)
for x in digits:
digitfreq[int(x)] += 1
lower = ("0" * added) + lower
l = []
assert self.dfs(l, digitfreq, lower, False)

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```
```

## 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

## 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

## 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