Postcard Mountain Skylines

MediumbacktrackingAlso known as Generate Parentheses

A designer draws simple mountain skylines for a set of postcards. The pen moves left to right in equal strokes, and each stroke goes either up a slope (U) or down one (D). A skyline starts on the horizon, ends on the horizon, and never dips below it, because the land cannot go underground. The card is short, so no point may rise more than maxHeight strokes above the horizon.

For a series with a fixed number of up-strokes, the designer wants one postcard for every skyline that fits. UUDD is one tall peak; UDUD is two small hills.

Your task

Write allSkylines(climbs, maxHeight). Return every string made of climbs letters U and climbs letters D where, reading left to right, the height (number of Us so far minus number of Ds so far) never drops below 0 and never goes above maxHeight.

Return the strings in any order, each exactly once. If no skyline fits, return an empty list. For climbs = 0 the only skyline is the flat horizon, the empty string, so return [""].

allSkylines(climbs: int, maxHeight: int) → string[] Any order of the returned list is accepted.

Examples

Example 1

Input

climbs = 2
maxHeight = 2

Output

["UUDD", "UDUD"]

Why

Two Us and two Ds can be arranged 6 ways, but only 2 stay above the horizon. UDDU goes below after its third stroke, and DUUD goes below on its first. Both survivors reach at most height 2, so they fit.

Example 2

Input

climbs = 3
maxHeight = 2

Output

["UUDUDD", "UUDDUD", "UDUUDD", "UDUDUD"]

Why

Without a height limit there would be 5 skylines. The fifth, UUUDDD, climbs to height 3, which is taller than the card allows.

Example 3

Input

climbs = 0
maxHeight = 0

Output

[""]

Why

No strokes at all. There is still one postcard, showing a flat horizon, so the answer has one empty string in it.

Constraints

0 ≤ climbs ≤ 8
0 ≤ maxHeight ≤ 8
Strings may be returned in any order.

Start with brute force

Generate all 2²ⁿ strings of U and D, then keep the ones that stay between the horizon and the height limit and end on the horizon. For climbs = 8 that is 65,536 strings checked to keep at most 1,430, and the share of waste keeps growing with n.

Most rejected strings were doomed after a stroke or two: the ones starting with D alone are half of all strings. Checking at the end means building every one of them in full first.

Hints

0 of 4 shown

Hint 1
Write out the skylines for climbs = 2 by hand. Which first stroke is never allowed, and why?
Hint 2
Track the height as you draw. An up-stroke is allowed when you still have up-strokes left and the height is below maxHeight. A down-stroke is allowed only when the height is above 0. Nothing else can go wrong.
Hint 3
So build each skyline one stroke at a time, and only ever add a stroke that is allowed. A recursive helper draw(sky, upsLeft, height) tries U and then D, each only when its rule allows it.
Hint 4
When the string reaches length 2 × climbs, record it. You do not need to check it: all up-strokes are used, so all down-strokes are too, and the height is 0. Passing sky + 'U' builds a new string, so there is nothing to undo after the call.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Instead of building strings and then rejecting the bad ones, never take a stroke that breaks a rule. Two numbers decide what is allowed next: how many up-strokes are left, and the current height.

Trace climbs = 2, maxHeight = 2. Each line is (sky, upsLeft, height):

("", 2, 0): height is 0, so only U is allowed.
("U", 1, 1): both are allowed. Try U first.
("UU", 0, 2): no ups left (and the card's top is reached), so D, then D again. Record UUDD.
Back at ("U", 1, 1), try D: ("UD", 1, 0). Height 0, so only U, then D. Record UDUD.

With maxHeight = 1 the second line would allow only D, and UUDD would never be started. As long as maxHeight is at least 1, every partial skyline built this way can still be finished, so no work is thrown away. The usual mistake is checking only that the counts match at the end, which lets DU through.

Reference solution

function allSkylines(climbs, maxHeight) {
  const skylines = [];
  function draw(sky, upsLeft, height) {
    if (sky.length === 2 * climbs) {
      skylines.push(sky); // complete, and back on the horizon
      return;
    }
    if (upsLeft > 0 && height < maxHeight) draw(sky + 'U', upsLeft - 1, height + 1);
    if (height > 0) draw(sky + 'D', upsLeft, height - 1); // stay above
  }
  draw('', climbs, 0);
  return skylines;
}

def all_skylines(climbs, max_height):
    skylines = []
 
    def draw(sky, ups_left, height):
        if len(sky) == 2 * climbs:
            skylines.append(sky)  # complete, and back on the horizon
            return
        if ups_left > 0 and height < max_height:  # room to climb
            draw(sky + 'U', ups_left - 1, height + 1)
        if height > 0:            # only go down if above the horizon
            draw(sky + 'D', ups_left, height - 1)
 
    draw('', climbs, 0)
    return skylines

TimeO(4ⁿ / √n)The number of skylines (the Catalan numbers) grows like 4ⁿ / n^1.5, each takes O(n) to build, and no dead-end string is ever started.

SpaceO(n)The recursion is 2n calls deep, not counting the output.

Learn the idea: Backtracking Recursion

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code