Bit String Bijection I am searching for a bijection between two types of bit strings (strings of $0$'s and $1$'s) both of even length $(2n).$
The restriction on the first type of bit string is that they must have the same number of $0$'s and $1$'s.
The restriction on the second type is that they can not have any prefix with the same number of $0$'s and $1$'s.
Note that I need the actual bijection, it is not enough to simply show that they are in bijection with one another. So I need both a transformation and it's inverse.
This is a sub-problem of a larger problem that I have been working on for some time now and it is the last piece that I have been unable to work out.  Thanks in advance for any help.
If any additional clarification or if examples would be helpful, just let me know and I'd be happy to provide it
 A: We can think about both problems by filling up a number from the left and progessively “taking choice away“. I'll detail a construction for numbers starting with a $0$ (both of type 1 and type 2) but the algorithm can be mirrored for numbers with an initial $1$.
I'll call numbers with an equal amount of zeroes and ones „balanced“ and numbers of the other type “leaving”. (The sum $\sum_{i=0}^k (2a_i-1)$ starts $0$, then leaves and never returns for a growing $k$.)
Mapping “balanced” numbers to “leaving” numbers, first some examples:
$$001011 → 001001; 011100 → 000110$$
$$000111 → 001010; 010101 → 000000$$
So how does this construction work? As mentioned, the result is build by emitting digit after digit while the input is slowly consumed. This may happen at different speeds. During this we will need to remember one core variable: $$δ = \text{the amount of consumed zeroes - the amount of consumed ones}$$
The remaining amount of input $ρ$ is also important. In particular, when $ρ=δ$ holds, all remaining digits of the input are already defined! The input doesn't tell us anything more. At this point we should already have constructed the final output. Finally, we want to know
$$s = \text{amount of emited zeroes} - \text{amount of emited ones.}$$
This is important, as we must always insure that $s \geq 1$, and when $s = 1$ we are forced to emit a $0$.
Here is the algorithm:
Input | is δ > 0? | What to emit
    0 |    NO     |      0
    0 |   YES     |      1
    1 |    NO     |      1
    1 |   YES     |      0

Here is an example run on 001011:
Remaining input | read | δ | s | ρ | emited output
  001011        |  --  | 0 | 0 | 6 |  nothing
   01011        |   0  | 1 | 1 | 5 |  0
   01011        |  --  | 1 | 2 | 5 |  00      // because s=1 forces us
    1011        |   0  | 2 | 1 | 4 |  001
    1011        |  --  | 2 | 2 | 4 |  0010    // forced by s=1
     011        |   1  | 1 | 3 | 3 |  00100
      11        |   0  | 2 | 2 | 2 |  001001  // now δ=ρ, terminate

What is the Idea behind all this?
This bijection is about mannaging the remaining choice left. For balanced numbers, taking future choice away means picking a number that is already more numerous. For leaving numbers, taking future choice away means moving closer to equilibrium. So the algorithm is fundamentaly about deciding if a move is pro-choice or reducing-choice and translating that. The no-choice moves are weaved inbetween.
What is left to do?
You still have to show that this is well defined and actually a bijection.(construct the inverse, it's fun!)
