Fill placeholders in a template string

Write a function that fills in a template string.

def format_template(template: str, keys: list[str], values: list[str]) -> str

template may contain placeholders written as {name}. The text between the braces is a variable name. keys[i] is a variable name and values[i] is the text that replaces it. Return the template with every placeholder replaced by its value. Copy all characters outside placeholders unchanged.

You may assume:

• every { has a matching }, and placeholders are not nested;
• every name used in template appears in keys;
• keys and values have the same length.

A replacement value is plain text. If a value itself contains something like {x}, it is not expanded again.

Constraints: 0 <= len(template) <= 10^5, 0 <= len(keys) <= 10^4.

Example 1

template = "Order {id} ships to {city} on {day}."
keys     = ["city", "id", "day"]
values   = ["Lisbon", "A-17", "Tuesday"]
→ "Order A-17 ships to Lisbon on Tuesday."

Example 2

template = "{greet}{greet}, {name}"
keys     = ["greet", "name"]
values   = ["hey", "{greet}"]
→ "heyhey, {greet}"

The value of name is copied as it is, so its braces stay in the output.

Reconstructed from the reported question; details may differ from what interviewers ask.