The goal of Notched Wood Bars puzzle is to complete the square lattice by inserting the given bars into each other. Each element of the puzzle is a rectangular bar with two or more notches. Each notch has only two kinds of depth, either shallow or deep.
The lattice has to be constructed by inserting the bars vertically from below and horizontally from above or vice versa, matching each shallow notch with a deep one. Each bar can therefore be oriented with the notches facing upwards or downwards.
You have 2*K bars in the puzzle, each with K notches, and you must determine the number of ways the lattice can be constructed. Notice that you must count only distinct configurations. Two configurations are considered distinct if one is not a rotation of the other. More specifically, if one configuration can be rotated in any way (in all three dimensions) such that all of its pieces exactly coincide with identical pieces in another configuration, then the two configurations are not distinct.
You will be given a String bars. Each element of bars represents the notches on a single bar. 'S' represents a shallow notch, and 'D' represents a deep notch. Return the number of distinct ways to complete the puzzle, or 0 if the puzzle is incorrect and cannot be completed.