TopCoder - SRM 144 - Div 2 - 550 Pt

From Single Round Match No. 144 of TopCoder's Algorithm Competition:
Write a method decode that, given a string which represents an encoded binary string, where the encoding method dictates bitenc[i] = bitorig[i-1] + bitorig[i] + bitorig[i+1], returns a string[] containing the two possible original binary strings. These two possible originals are yielded by assuming either bitorig[0] == 0 or bitorig[0] == 1. If the encoded string cannot be produced via an assumption, return "NONE" in place of a binary string.
(Full problem specification is copyright TopCoder; and, can be found in the TopCoder problem archives.)

Solution.
Unit Tests For Sample Data.

This problem was used as the Division 2 550-point problem and as the Division 1 300-point problem. The solution here is to rearrange bitenc[i] = bitorig[i-1] + bitorig[i] + bitorig[i+1] to yield bitorig[j] = bitenc[j-1] - bitorig[j-1] - bitorig[j-2]. Then once we generate our original, we only have to verify that bitenc[ilast] == bitorig[ilast-1] + bitorig[ilast] (and that the original contains only binary digits).