Binary String MEX - CodeChef Solution in Java| AskTheCode

CodeChef April Long Challenge Solution | Binary String MEX (MEXSTR) solution | AskTheCode

---

Problem:

You are given a binary string S. Chef defines MEX(S) as the smallest non-negative integer such that its binary representation (without leading '0'-s; in particular, the binary representation of 0 is "0") is not a subsequence of S.

Chef is asking you to find MEX(S). Since this integer could be very large, find its binary representation (without leading '0'-s).

---

Input:

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

• The first and only line of each test case contains a single string S.

---

Output:

For each test case, print a single line containing one string: MEX(S) in binary representation.

---

Example Input:

2 1001011 1111

---

Example Output:

1100 0

---

Explanation:

Example case 1: All integers between 0 and 11 inclusive, in binary representation, appear in S as subsequences. However, the binary representation of 12 (which is "1100") is not a subsequence of S.

Example case 2: Since S contains only '1'-s, the string "0" is not a subsequence of S and therefore MEX(S)=0.

---

Code:

/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	 public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
      
        int t=sc.nextInt();
        while(t-->0){

           String s=sc.next();
            char str[]=new char[s.length()];
            for(int i=0;i<str.length;i++) {
                char c=s.charAt(i);
                str[i] = c;
            }
            boolean lz=false;
            int ind=0;
            while (ind<str.length&&str[ind]=='0'){
                lz=true;
                ind++;

            }
            char str_new[]=new char[str.length-ind];
            for(int i=ind;i<str.length;i++)
                str_new[i-ind]=str[i];
            String ans=mex(str_new);
            if(ans.equals("10")) ans="0";
            if(ans.equals("01")) ans="1";
            if(ans.equals("0")&&lz) ans="10";
            System.out.println(ans);
        }
    }
    public static String mex(char s[]){
        if(s.length==0) return "1";
        if(s.length==1&&s[0]=='0') return "1";
        if(s.length==1&&s[0]=='1') return "0";
        int n=s.length;
        int dp[][]=new int[2][n+2];
        int l1i=n+1;
        int l0i=n;
        dp[0][n]=-1;
        dp[1][n]=1;
        dp[0][n+1]=-1;
        dp[1][n+1]=1;
        for(int i=n-1;i>=0;i--){
            int ind=findmin(l0i,l1i,dp);
            dp[0][i]=ind;
            dp[1][i]=dp[1][ind]+1;
            if(s[i]=='0') l0i=i;
            else l1i=i;
        }
        int i=0;
        StringBuffer sb=new StringBuffer("");
        while(i!=-1){
            if(i==n) sb.append('0');
            else if(i==n+1) sb.append('1');
            else sb.append(s[i]);
            i=dp[0][i];
        }
        return sb.toString();
    }
    public static int findmin(int z,int o,int dp[][]){

        return (dp[1][z]<=dp[1][o])?z:o;
    }
}