Quick Overview

Implement a template filler that replaces every key wrapped in percent signs, such as %A% in %A%_%B%, with its value from a dictionary. It tests left-to-right scanning, pairing of delimiters, single-pass replacement that never rescans inserted values, and efficient string building.

Fill %KEY% Placeholders in a Template String from a Dictionary

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given a template string `text` and a dictionary `mapping` from keys to values, return the string obtained by replacing every placeholder in `text` with the value of its key. A placeholder is a key wrapped in percent signs: with `mapping = {"A": "abc", "B": "def"}`, the text `%A%_%B%` becomes `abc_def`. The report gives this example and states that a key in the text is always wrapped in `%` on both sides; this version fixes the remaining details in Rules below. ### Function Signature ```python def substitute(text: str, mapping: dict[str, str]) -> str: ``` ### Rules - Every `%` in `text` is a placeholder delimiter. Reading left to right, the first and second `%` enclose one key, the third and fourth enclose the next key, and so on. The number of `%` characters in `text` is even. - Every key is nonempty: two `%` characters that are paired with each other are never adjacent. (A closing `%` may be immediately followed by the opening `%` of the next placeholder, as in `%X%%X%`.) - Every key that appears in `text` is a key of `mapping`. Keys of `mapping` that do not appear in `text` are ignored, and a key may appear in `text` any number of times. - Each placeholder, including both of its `%` characters, is replaced by `mapping[key]`. Every character outside placeholders is copied unchanged and in order. - Replacement is a single pass: inserted values are never scanned for placeholders again. Values never contain `%`. - Return the resulting string. ### Constraints - `0 <= len(text) <= 10^5` - `1 <= len(mapping) <= 1000` - Every key has 1 to 20 characters, each an ASCII letter, digit or underscore. - Every value has 0 to 100 printable ASCII characters, none of them `%`. - `text` consists of printable ASCII characters (spaces included), and the characters between each pair of matched `%` form a key of `mapping`. - The returned string has at most `10^6` characters. ### Examples **Example 1** ```text Input: text = "%A%_%B%", mapping = {"A": "abc", "B": "def"} Output: "abc_def" ``` `%A%` becomes `abc`, the underscore is copied, and `%B%` becomes `def`. **Example 2** ```text Input: text = "Hello, %NAME%! You have %N% new messages.", mapping = {"NAME": "Ada", "N": "3", "UNUSED": "x"} Output: "Hello, Ada! You have 3 new messages." ``` The key `UNUSED` never appears in the text and has no effect. **Example 3** ```text Input: text = "%X%%X%-%Y%", mapping = {"X": "ab", "Y": ""} Output: "abab-" ``` The `%` characters sit at positions 0, 2, 3, 5, 7 and 9, so they pair as (0, 2), (3, 5) and (7, 9), enclosing the keys `X`, `X` and `Y`. The two `X` placeholders each become `ab`, the hyphen is copied, and `Y` maps to the empty string.

Overview: Implement a template filler that replaces every key wrapped in percent signs, such as %A% in %A%_%B%, with its value from a dictionary. It tests left-to-right scanning, pairing of delimiters, single-pass replacement that never rescans inserted values, and efficient string building.

Given a template string `text` and a dictionary `mapping` from keys to values, return the string obtained by replacing every placeholder in `text` with the value of its key. A placeholder is a key wrapped in percent signs: with `mapping = {"A": "abc", "B": "def"}`, the text `%A%_%B%` becomes `abc_def`. **Rules** - Every `%` in `text` is a placeholder delimiter. Reading left to right, the first and second `%` enclose one key, the third and fourth enclose the next key, and so on. The number of `%` characters in `text` is even. - Every key is nonempty: two `%` characters that are paired with each other are never adjacent. A closing `%` may be immediately followed by the opening `%` of the next placeholder, as in `%X%%X%`. - Every key that appears in `text` is a key of `mapping`. Keys of `mapping` that do not appear in `text` are ignored, and a key may appear in `text` any number of times. - Each placeholder, including both of its `%` characters, is replaced by `mapping[key]`. Every character outside placeholders is copied unchanged and in order. - Replacement is a single pass: inserted values are never scanned for placeholders again. Values never contain `%`. Return the resulting string. Both arguments and the return value are strings; no numeric value is passed or returned. **Constraints** - `0 <= len(text) <= 10^5` - `1 <= len(mapping) <= 1000` - Every key has 1 to 20 characters, each an ASCII letter, digit or underscore. - Every value has 0 to 100 printable ASCII characters, none of them `%`. - `text` consists of printable ASCII characters (spaces included), and the characters between each pair of matched `%` form a key of `mapping`. - The returned string has at most `10^6` characters. **Example 1** ``` Input: text = "Hello, %NAME%! You have %N% new messages.", mapping = {"NAME": "Ada", "N": "3", "UNUSED": "x"} Output: "Hello, Ada! You have 3 new messages." ``` `%NAME%` becomes `Ada` and `%N%` becomes `3`; every other character is copied. The key `UNUSED` never appears in the text and has no effect. **Example 2** ``` Input: text = "%X%%X%-%Y%", mapping = {"X": "ab", "Y": ""} Output: "abab-" ``` The `%` characters sit at positions 0, 2, 3, 5, 7 and 9, so they pair as (0, 2), (3, 5) and (7, 9), enclosing the keys `X`, `X` and `Y`. The two `X` placeholders each become `ab`, the hyphen is copied, and `Y` maps to the empty string.

Constraints

  • 0 <= len(text) <= 10^5
  • 1 <= len(mapping) <= 1000
  • Every key has 1 to 20 characters, each an ASCII letter, digit or underscore.
  • Every value has 0 to 100 printable ASCII characters, none of them '%'.
  • text consists of printable ASCII characters (spaces included), and the characters between each pair of matched '%' form a key of mapping.
  • The number of '%' characters in text is even, and two '%' characters paired with each other are never adjacent.
  • The returned string has at most 10^6 characters.

Examples

Input: ('%A%_%B%', {'A': 'abc', 'B': 'def'})

Expected Output: 'abc_def'

Explanation: Source example 1: both placeholders are replaced and the underscore between them is copied.

Input: ('Hello, %NAME%! You have %N% new messages.', {'NAME': 'Ada', 'N': '3', 'UNUSED': 'x'})

Expected Output: 'Hello, Ada! You have 3 new messages.'

Explanation: Source example 2: text is exactly 41 characters, output exactly 36; the unused key UNUSED has no effect.

Hints

  1. Which '%' closes a placeholder depends only on the order of the '%' characters in text, never on the contents of mapping.
  2. Characters outside placeholders are copied as they are, even when they happen to spell a key name, and an inserted value is never examined again.
  3. A substring that looks like %KEY% is not necessarily a placeholder: check where it sits in the left-to-right pairing.

Loading coding console...

Show the approach

Approach

Scan text left to right with an index i that always sits outside every placeholder. Find the next % at or after i, at position j; everything in text[i:j] is ordinary text and is copied as is. Because % characters pair strictly in order and text[:i] holds an even number of them, the % at j opens a placeholder and the next % after it, at position k, closes it, so text[j+1:k] is the key. Append mapping[key] and continue from k + 1. When no % remains, copy the rest of text and stop.

Invariant: at the top of the loop, text[:i] contains an even number of % characters and the pieces collected so far are exactly the substitution of text[:i]. Each step extends i past either the remaining plain text or one ordinary run plus one complete placeholder, preserving the invariant, so at the end the collected pieces are the substitution of the whole text.

The key is delimited by the closing %, never matched against the dictionary, so a key that is a prefix of another (A and AB) cannot be confused, and a key name that appears outside delimiters is never looked up. A substring such as %B% formed by a closing %, plain text and the next opening % is not a placeholder, which is why replacing keys one at a time in dictionary order is wrong. Inserted values are appended once and never rescanned, which is exactly the single-pass rule. Pieces are collected and joined once, so building the output is linear rather than quadratic.

Edge cases: empty text returns the empty string; text without % is returned unchanged; an empty value makes its placeholder vanish; back-to-back placeholders such as %X%%X% work because the search for the next opening % starts right after the previous closing one; unused mapping keys are never touched.

Time complexity:
O(n + L), where n = len(text) and L is the length of the returned string
Space complexity:
O(L) for the output pieces