Solve array duplicate flags and binary swaps

Problem 1: Flag duplicates on the left and right

You are given an integer array nums of length n.

For each index i, determine:

1. Left-duplicate: whether nums[i] has appeared in any index < i.
2. Right-duplicate: whether nums[i] appears in any index > i.

Construct two binary strings of length n:

• left[i] = '1' if nums[i] appears in nums[0..i-1], else '0'.
• right[i] = '1' if nums[i] appears in nums[i+1..n-1], else '0'.

Return [left, right].

Example

• Input: nums = [5, 1, 5, 2, 1]
• Output:
  • left = "00101" (the second 5 and the second 1 have appeared on the left)
  • right = "10110" (the first 5 and first 1 appear again on the right)

Constraints (typical): 1 ≤ n ≤ 2e5, nums[i] fits in 32-bit signed integer.

---

Problem 2: Synchronous replacement "01" → "10" until stable

You are given a binary string s (characters are only '0' and '1').

Each second, all occurrences of substring "01" are replaced simultaneously with "10".

• This is a synchronous update: replacements in the same second do not affect each other.

Repeat this process until the string contains no "01".

Return the number of seconds required.

Example

• Input: s = "010110"
• Output: ? (compute the number of synchronous steps until no "01" remains)

Notes: A direct step-by-step simulation can be too slow for large strings; the intended solution should account for interactions where multiple '1's can “block” each other.

Constraints (typical): 1 ≤ |s| ≤ 2e5.

Flag duplicates on the left and right

You are given an integer array nums of length n.

For each index i, determine two things:

1. Left-duplicate: whether nums[i] has already appeared at some index < i.
2. Right-duplicate: whether nums[i] appears again at some index > i.

Build two binary strings of length n:

• left[i] = '1' if nums[i] appears in nums[0..i-1], else '0'.
• right[i] = '1' if nums[i] appears in nums[i+1..n-1], else '0'.

Return the pair [left, right].

Example

• Input: nums = [5, 1, 5, 2, 1]
• left = "00101" — the second 5 (index 2) and the second 1 (index 4) have each appeared earlier.
• right = "11000" — index 0's 5 recurs later (at index 2) and index 1's 1 recurs later (at index 4); the remaining values never recur to their right.

Note: an earlier draft of this prompt listed right = "10110", but that is inconsistent with the definition above ("appears at any index > i"). The definition-correct answer is "11000".

Constraints: 1 ≤ n ≤ 2·10^5, each nums[i] fits in a 32-bit signed integer.

Constraints

• 1 ≤ n ≤ 2·10^5
• Each nums[i] fits in a 32-bit signed integer
• Output strings have exactly length n, characters only '0' or '1'

Hints

1. A single left-to-right pass with a hash set of already-seen values fills left: before inserting nums[i], check whether it is already in the set.
2. Symmetrically, a right-to-left pass with a fresh hash set fills right: before inserting nums[i], check whether it is already in the set.
3. Two linear passes give O(n) time; no nested loops needed.

Synchronous "01" → "10" replacement until stable

You are given a binary string s containing only '0' and '1'.

Each second, every occurrence of the substring "01" is replaced simultaneously by "10". The update is synchronous: all replacements within one second use the string as it was at the start of that second, so overlapping/adjacent replacements in the same second do not chain.

Repeat until the string contains no "01" (i.e. it becomes all 1s followed by all 0s). Return the number of seconds the process takes.

Example

• Input: s = "010110"
• Step 1: "010110" → "101010"
• Step 2: "101010" → "110100"
• Step 3: "110100" → "111000" (stable)
• Output: 3

A naive step-by-step simulation is O(n²) in the worst case (e.g. "000…0111…1"). The intended O(n) solution reasons about how each '1' is delayed ("blocked") by the '1's ahead of it.

Constraints: 1 ≤ |s| ≤ 2·10^5.

Constraints

• 1 ≤ |s| ≤ 2·10^5
• s contains only the characters '0' and '1'
• Return 0 when s is already stable (no "01" substring)

Hints

1. Think of each '1' moving left past the '0's in front of it. A '1' with no '0' before it never moves and contributes 0.
2. Scan left to right tracking the number of zeros seen so far. When you reach a '1' that has at least one zero before it, its finish time is at least zeros (it must hop over that many zeros) but also at least one more than the previous '1''s finish time, because the previous '1' can block it for a second.
3. So maintain t = max(t + 1, zeros) at each '1' (only when zeros > 0); the answer is the final t. This is O(n) and avoids the O(n²) simulation blowup.