# Facebook 2 hr coding challenge (Magical String)

• A binary string is a string consisting only of 0's and/or 1's.

For example, 01011, 1111, and 00 are all binary strings. The prefix of a string is any substring of the string that includes the beginning of the string. For example, the prefixes of 11010 are 1, 11, 110, 1101, and 11010.

We consider a non-empty binary string to be magical if the following two conditions are true:

1. The number of 0's is equal to the number of 1's.
2. For every prefix of the binary string, the number of 1's should not be less than the number of 0's.

For example, 11010 is not magical because it doesn't have an equal number of 0's and 1's, but 110100 is magical because it satisfies both of the above conditions.

A magical string can contain multiple magical substrings. If two consecutive substrings are magical, then we can swap the substrings as long as the resulting string is still a magical string. Given a magical binary string, binString, perform zero or more swap operations on its consecutive magical substrings such that the resulting string is as lexicographically large as possible.

Two substrings are considered to be consecutive if the last character of the first substring occurs exactly one index before the first character of the second substring.

Function Description Complete the largestMagical function in the editor below. Parameter Name Type Description binString String The input binary string. Return The function must return a string denoting the lexicographically largest possible magical string that can be formed by performing zero or more swap operations on consecutive magical substrings of binString.

It is guaranteed that binString is a binary string of 1's and 0's only. 1 ≤ the length of the string ≤ 50 It is guaranteed that binString is a magical string.
Input Format For Custom Testing Sample

Case 0 Sample Input For Custom Testing 11011000
Sample Output 11100100

Explanation :
Given the magical string binString = 1 10 11000, we can choose two consecutive magical substrings, 1100 and 10, to swap such that the resultant string, str = 11100 10 0, is the lexicographically largest possible magical string possible. Thus, we return the value of str, which is 11100100, as our answer.

Test case 1:
input - 11011000
output - 11100100

Test case 2 :
Input - 1100
output - 1100

Test case 3:
Input :1101001100
Output : 1101001100

• May I ask how to deal with lexicographically largest string for negative strings?

• ``````public static String largestMagical(String str) {
int length = str.length();
int charIdx = 0;
while (charIdx < length) {
ArrayList<int[]> magicalList = findMagicalStr(str, charIdx);
int lengthMagicalList = magicalList.size();
if (lengthMagicalList != 0) {
String maxStr = str;
for (int i = 0; i < lengthMagicalList - 1; i++) {
for (int j = i + 1; j < lengthMagicalList; j++) {
int inter2[] = { magicalList.get(i)[1] + 1, magicalList.get(j)[1] };
for (int k = i; k >= 0; k--) {
int inter1[] = { magicalList.get(k)[0], magicalList.get(i)[1] };
String strSwap = swapString(inter1, inter2, str);
if (strSwap.compareTo(maxStr) > 0) {
maxStr = strSwap;
}
}
}
}
str = maxStr;
}
charIdx++;
}

return str;
}

public static String swapString(int inter1[], int inter2[], String curStr) {
return curStr.substring(0, inter1[0]) + curStr.substring(inter2[0], inter2[1] + 1)
+ curStr.substring(inter1[0], inter1[1] + 1) + curStr.substring(inter2[1] + 1);
}

public static ArrayList<int[]> findMagicalStr(String s, int start) {
ArrayList<int[]> magicalList = new ArrayList<>();
int j = start;
int length = s.length();
int numOfZeros = 0;
int numOfOnes = 0;
char str[] = s.toCharArray();
for (int i = start; i < length; i++) {
if (str[i] == '1') {
numOfOnes += 1;
} else {
numOfZeros += 1;
}

if (numOfZeros > numOfOnes) {
break;
}
if (numOfZeros == numOfOnes && numOfZeros != 0) {
int arr[] = new int[] { j, i };
j = i + 1;
}
}
return magicalList;
}
``````

• ``````public class MagicalString {

private static void swap(final char[] input, int start, int end) {
char[] temp = {input[start], input[start + 1]};
for (int i = start + 2; i <= end; i++) {
input[i - 2] = input[i];
}
input[end - 1] = temp[0];
input[end] = temp[1];
}

private static int getNextMS(final char[] input, int start) {
for (int i = start, numZero = 0, numOne = 0; i < input.length; i++) {
if (i < start + 2 && input[i] != '1') return -1;
if (input[i] == '1') numOne++;
else numZero++;
if (numZero == numOne) return i;
}
return -1;
}

private static String largestMagical(final String binString) {
char[] input = binString.toCharArray();

for (int i = 1; i < input.length - 1; i++) {
if (input[i] == '0') {
int nextMS = getNextMS(input, i + 1);
if (nextMS != -1) swap(input, i - 1, nextMS);
}
}
return String.copyValueOf(input);
}

public static void main(String[] args) {
String binString = "11011000";
System.out.println(largestMagical(binString));
}
}
``````

• @CSU2018 what negative strings? It is guaranteed that string will always have 0s and 1s only

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.