# It's possible to solve this problem in $O(n)$?

Suppose given two strings $$s_1$$ and $$s_2$$ each of length $$n$$.

We consider $$s_1$$ and $$s_2$$ as dual, if one of the following conditions satisfied:

1. Strings are equal.

2. Else, if $$n$$ is even then:

Divide $$s_1$$ into two equal partitions $$a_1,a_2$$, also divide $$s_2$$ into $$b_1,b_2$$ then:

• $$a_1$$ with $$b_1$$ and $$a_2$$ with $$b_2$$ are dual.
• Or $$a_1$$ with $$b_2$$ and $$a_2$$ with $$b_1$$ are dual.

The description above implies a recursive algorithm in $$O(n\log n)$$. But my question is that, is it possible to solve the problem in $$O(n)$$?

• "Divide $s_1$ into two equal partition $a_1$, $a_2$" - does it mean that the length of $s_1$ is even and $a_1$ is the first half of $s_1$ and $a_2$ is the second half of $s_1$? How can it be solved in $O(n \log n)$? I see $O(n^2)$ algorithm. where running time is given by recurrence $T(n) = 4 T(\frac n2) + O(1)$. Nov 17 at 9:22
• You can probably solve it in $O(n)$ by using hashes: for string $s$, which consist of two parts $\alpha_1$ and $\alpha_2$, you can recursively compute $h(s) = h'(h(\alpha_1), h(\alpha_2))$, where $h'$ is some symmetric hash-function. If you properly select $h'$, it should be correct with high probability (it can only result if false-positive, and you can always check it). Nov 17 at 10:39