I was asked this in phone screen for Facebook. Could solve it only by bruteforce/backtracking. Is there any efficient solution to this? \n\nProblem: Given a binary string S, one has to find another binary string which is not a subsequence of S such that its length is minimal and is lexicographically smallest possible.\n\n**Example 1:**\n```\nInput: "00101"\nOutput: "100"\n```\n\n**Example 2:**\n```\nInput: "1111"\nOutput: "0"\n```\n\n**Example 3:**\n```\nInput: "00010000"\nOutput: "11"\n```

I was asked this in phone screen for Facebook. Could solve it only by bruteforce/backtracking. Is there any efficient solution to this? \n\nProblem: Given a bin