Solution


Approach 1: Brute Force

Intuition

Let's create every possible string - then we can compare them and choose the best one.

Algorithm

In our depth first search, we will maintain sb (or A in Python), the contents of a path from the root to this node.

When we reach a leaf, we will reverse this path to create a candidate answer. If it is better than our current answer, we'll update our answer.

Complexity Analysis

  • Time Complexity: We use to traverse the array and maintain A [Python] or sb. Then, our reversal and comparison with the previous answer is , where is the size of the string we have when at the leaf. For example, for a perfectly balanced tree, and the time complexity would be .

  • Space Complexity: .


Analysis written by: @awice.