Given two strings A and B of equal length with characters from the set {1,2}. A string S is a good string if you move exactly S[i] steps forward or backward at i’th position and ended at the last position such that you covered all positions exactly once. Given two good strings A and B, you have to tell the number of possible swapping between the corresponding positions in the strings such that the strings remain good.

Example: A = 2211 B = 1111

Answer : 8 Correct swappings {}, {1, 2}, {1, 2, 3}, {1, 2, 4}, {1, 2, 3, 4}, {3}, {4}, {3, 4}

Please help me optimize the approach. Currently I am able to think of the brute solution in which we can generate all the subsequence and then perform swapping on the strings and after that checking whether the string is good or not. Time complexity = O(n*(2^n))

Is there any way to optimize the solution.