Joints in the kiln lining

A pottery kiln is being relined, and brickwork grows as it heats. A panel laid without symmetry pushes harder on one side and lifts.

The problem

The lining is one course of firebrick laid end to end. Each brick is a single grade, written as one letter — h high-alumina, s silica, f fireclay. The course is the string of those letters, door to back.

A stretch of course is matched when its grades pair off about the centre: the first brick with the last, the second with the second from the end, and so on inward. hffh is matched; hff is not. A single brick is matched on its own.

Expansion joints fall between bricks, never through one, and every panel they leave must be matched. Report the fewest joints — joints, not panels. A course matched end to end needs none; a course with no grade repeated needs a joint between every brick.

Input. course — a non-empty string of lowercase letters, the grades in order along the lining.

Output. The smallest number of joints.

Example.

course = "hhsfs"   ->  1

A joint after the second brick leaves hh and sfs, both matched. Zero is out: hhsfs pairs h against s at the two ends.

A second example, where the longest matched run at the front is the wrong opening:

course = "hhfhss"   ->  2

Taking hh first strands f and h as single bricks — three joints. Cutting after the first brick instead gives h, hfh and ss, which is two.

A third example, needing nothing:

course = "hsfsh"   ->  0

Constraints.

• 1 <= len(course) <= 2000
• every character is a lowercase letter

Hints

Approach

Brute force

Pick a subset of the gaps to open and check each panel it produces: 2ⁿ⁻¹ subsets at O(n) each. Twenty bricks is a million checks; the lining runs to two thousand.

The insight

Whether a stretch is matched depends on that stretch and nothing else, so settle every stretch once and the joints become a single left-to-right scan.

Symmetry has a recurrence of its own: course[i..j] is matched exactly when course[i] == course[j] and course[i+1..j-1] is matched. Filled from short stretches outward, that table costs O(n²) once and never consults the joints. The scan then asks only where the last panel begins, and every shorter prefix it needs is already answered, because that prefix stops to the left.

Algorithm

1. Fill matched[i][j] for every stretch, running i downward and j upward, so matched[i+1][j-1] is written before it is read.
2. Let joints[j] be the fewest joints for the first j + 1 bricks.
3. If matched[0][j], then joints[j] = 0 — the prefix is one panel.
4. Otherwise take the smallest joints[i-1] + 1 over each i in 1..j for which matched[i][j] holds.
5. The answer is joints[n-1].

Complexity

Time O(n²) — about n²/2 table entries at O(1) each, then n²/2 lookups in the joint scan: near 4 · 10⁶ steps at two thousand bricks. Space O(n²) for the table, plus O(n) for the joint array.

Solution

"""Joints in the kiln lining — a symmetry table, then fewest joints per prefix."""


def solve(course):
    n = len(course)
    if n < 2:
        return 0

    # matched[i][j] is True when the stretch course[i..j] pairs off about its
    # centre; short stretches settle first, so matched[i+1][j-1] is ready
    matched = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if course[i] == course[j] and (j - i < 2 or matched[i + 1][j - 1]):
                matched[i][j] = True

    # joints[j] = fewest joints that split course[0..j] into matched panels
    joints = [0] * n
    for j in range(n):
        if matched[0][j]:
            continue                      # no joint at all: the prefix is one panel
        best = j                          # worst case: a joint after every brick
        for i in range(1, j + 1):
            if matched[i][j] and joints[i - 1] + 1 < best:
                best = joints[i - 1] + 1
        joints[j] = best
    return joints[n - 1]

TESTS = [
    (("hhsfs",), 1),
    (("hhfhss",), 2),
    (("hsfsh",), 0),
    (("h",), 0),
    (("hsf",), 2),
    (("ss",), 0),
    (("hsshffhsfsh",), 2),
    (("hffhsshffs",), 2),
    (("f" * 400,), 0),
]

Pitfalls

• Testing symmetry inside the joint loop by comparing a slice against its reverse turns O(n²) into O(n³): seconds become minutes at the stated bound.
• Filling the table in the wrong order. matched[i][j] reads matched[i+1][j-1], so running i upward reads an entry still false. Only single bricks and adjacent equal pairs survive, and hsfsh comes back as four joints instead of none.
• Counting panels rather than joints. A course already matched end to end answers 0, not 1, and the two differ by one everywhere else.

Variants

• The bead strand mirror — the same stretch table, read for the most items kept rather than for where to divide.
• Interval and matrix DP — the lesson behind a table filled by stretch length.