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.

Please help me solving this problem. I am not getting any idea how to proceed.

You are given an undirected weighed tree with N node . You need to find maximum absolute path sum in the tree with atmost k inversions. In one inversion you can change the weight of an edge from negative to positive and vice versa.