Description
Given an array of strings nums containing n unique binary strings each of length n, return a binary string of length n that does not appear in nums. If there are multiple answers, you may return any of them.
Example 1:
Input: nums = ["01","10"]
Output: "11"
Explanation: "11" does not appear in nums. "00" would also be correct.
Example 2:
Input: nums = ["00","01"]
Output: "11"
Explanation: "11" does not appear in nums. "10" would also be correct.
Example 3:
Input: nums = ["111","011","001"]
Output: "101"
Explanation: "101" does not appear in nums. "000", "010", "100", and "110" would also be correct.
Constraints:
n == nums.length1 <= n <= 16nums[i].length == nnums[i] is either '0' or '1'.- All the strings of
nums are unique.
Solutions
Solution 1: Counting + Enumeration
Since the number of '1's in a binary string of length n can be 0, 1, 2, …, n (a total of n + 1 possibilities), we can always find a new binary string whose count of '1's differs from every string in nums.
We use an integer mask to record the counts of '1's across all strings, where the i-th bit of mask being 1 indicates that a binary string of length n with exactly i occurrences of '1' exists in nums, and 0 otherwise.
We then enumerate i starting from 0, representing the count of '1's in a binary string of length n. If the i-th bit of mask is 0, it means no binary string of length n with exactly i occurrences of '1' exists, and we can return that string as the answer.
The time complexity is O(L), where L is the total length of all strings in nums. The space complexity is O(1).
PythonJavaC++GoTypeScriptJavaScriptC#
class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
mask = 0
for x in nums:
mask |= 1 << x.count("1")
for i in count(0):
if mask >> i & 1 ^ 1:
return "1" * i + "0" * (len(nums) - i)(code-box)
class Solution {
public String findDifferentBinaryString(String[] nums) {
int mask = 0;
for (var x : nums) {
int cnt = 0;
for (int i = 0; i < x.length(); ++i) {
if (x.charAt(i) == '1') {
++cnt;
}
}
mask |= 1 << cnt;
}
for (int i = 0;; ++i) {
if ((mask >> i & 1) == 0) {
return "1".repeat(i) + "0".repeat(nums.length - i);
}
}
}
}(code-box)
class Solution {
public:
string findDifferentBinaryString(vector<string>& nums) {
int mask = 0;
for (auto& x : nums) {
int cnt = count(x.begin(), x.end(), '1');
mask |= 1 << cnt;
}
for (int i = 0;; ++i) {
if (mask >> i & 1 ^ 1) {
return string(i, '1') + string(nums.size() - i, '0');
}
}
}
};(code-box)
func findDifferentBinaryString(nums []string) string {
mask := 0
for _, x := range nums {
mask |= 1 << strings.Count(x, "1")
}
for i := 0; ; i++ {
if mask>>i&1 == 0 {
return strings.Repeat("1", i) + strings.Repeat("0", len(nums)-i)
}
}
}(code-box)
function findDifferentBinaryString(nums: string[]): string {
let mask = 0;
for (let x of nums) {
const cnt = x.split('').filter(c => c === '1').length;
mask |= 1 << cnt;
}
for (let i = 0; ; ++i) {
if (((mask >> i) & 1) === 0) {
return '1'.repeat(i) + '0'.repeat(nums.length - i);
}
}
}(code-box)
/**
* @param {string[]} nums
* @return {string}
*/
var findDifferentBinaryString = function (nums) {
let mask = 0;
for (let x of nums) {
const cnt = x.split('').filter(c => c === '1').length;
mask |= 1 << cnt;
}
for (let i = 0; ; ++i) {
if (((mask >> i) & 1) === 0) {
return '1'.repeat(i) + '0'.repeat(nums.length - i);
}
}
};(code-box)
public class Solution {
public string FindDifferentBinaryString(string[] nums) {
int mask = 0;
foreach (var x in nums) {
int cnt = x.Count(c => c == '1');
mask |= 1 << cnt;
}
int i = 0;
while ((mask >> i & 1) == 1) {
i++;
}
return string.Format("{0}{1}", new string('1', i), new string('0', nums.Length - i));
}
}(code-box)
Solution 2: Construction
We can construct a binary string ans of length n, where the i-th bit of ans differs from the i-th bit of nums[i]. Since all strings in nums are distinct, ans will not appear in nums.
The time complexity is O(n), where n is the length of the strings in nums. Ignoring the space used by the answer string, the space complexity is O(1).
PythonJavaC++GoTypeScriptJavaScriptC#
class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
ans = [None] * len(nums)
for i, s in enumerate(nums):
ans[i] = "1" if s[i] == "0" else "0"
return "".join(ans)(code-box)
class Solution {
public String findDifferentBinaryString(String[] nums) {
int n = nums.length;
char[] ans = new char[n];
for (int i = 0; i < n; i++) {
ans[i] = nums[i].charAt(i) == '0' ? '1' : '0';
}
return new String(ans);
}
}(code-box)
class Solution {
public:
string findDifferentBinaryString(vector<string>& nums) {
int n = nums.size();
string ans(n, '0');
for (int i = 0; i < n; i++) {
ans[i] = nums[i][i] == '0' ? '1' : '0';
}
return ans;
}
};(code-box)
func findDifferentBinaryString(nums []string) string {
ans := make([]byte, len(nums))
for i, s := range nums {
if s[i] == '0' {
ans[i] = '1'
} else {
ans[i] = '0'
}
}
return string(ans)
}(code-box)
function findDifferentBinaryString(nums: string[]): string {
const n = nums.length;
const ans: string[] = new Array(n);
for (let i = 0; i < n; i++) {
ans[i] = nums[i][i] === '0' ? '1' : '0';
}
return ans.join('');
}(code-box)
/**
* @param {string[]} nums
* @return {string}
*/
var findDifferentBinaryString = function (nums) {
const n = nums.length;
const ans = new Array(n);
for (let i = 0; i < n; i++) {
ans[i] = nums[i][i] === '0' ? '1' : '0';
}
return ans.join('');
};(code-box)
public class Solution {
public string FindDifferentBinaryString(string[] nums) {
int n = nums.Length;
char[] ans = new char[n];
for (int i = 0; i < n; i++) {
ans[i] = nums[i][i] == '0' ? '1' : '0';
}
return new string(ans);
}
}(code-box)
