1101MediumArrayHash TableStringTrieString MatchingAho–Corasick Algorithm

Marking Up the Terms in a Line

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A line of text line and a list of terms are given. Wherever a term turns up inside line, that stretch of the line has to be wrapped between the markers <hi> and </hi>.

Stretches may overlap or sit flush against each other. Use as few pairs of markers as possible, so any stretches that overlap or touch end up inside a single pair.

Return the marked-up line.

Examples

Example 1

Input: line = "hello world", terms = ["lo", "wor"]
Output: "hel<hi>lo</hi> <hi>wor</hi>ld"

One term sits at the fourth letter and the other starts the second word. The two stretches neither touch nor overlap, so each takes its own pair of markers.

Example 2

Input: line = "abcdef", terms = ["cd", "de"]
Output: "ab<hi>cde</hi>f"

The two stretches share the letter d, so they go inside a single pair of markers rather than two.

Example 3

Input: line = "abc", terms = []
Output: "abc"

With no terms to look for the line comes back untouched.

Constraints

1 <= line.length <= 1000
0 <= terms.length <= 100
1 <= terms[i].length <= 1000
line and every term hold only English letters and digits
no two terms are the same

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def add_bold_tag(line: str, terms: list[str]) -> str:

Java

public String addBoldTag(String line, String[] terms)

The intended approach

Time O(n * total term length) for the matching plus O(n) for the write-out.Space O(n) for the flags and the pieces.

Deciding where the markers go and deciding which stretches match are two separate jobs, and keeping them apart is what makes the overlap rule easy. First, hold one flag per letter of the line saying whether that letter belongs to any matched stretch. For each term, find its every occurrence and raise the flags across it. Overlapping and touching stretches simply raise the same flags, so nothing special is needed for them. Then read the flags once from left to right. A run of raised flags is one marked stretch however many terms went into it, so open a marker at the start of a run, copy the letters, and close it where the run ends. Letters with a lowered flag are copied through untouched. Building the answer in pieces and joining them at the end avoids growing a string one letter at a time.

Pythonentry point: add_bold_tag

def add_bold_tag(line, terms):
    n = len(line)
    mark = [False] * n
    for term in terms:
        width = len(term)
        if width == 0 or width > n:
            continue
        start = line.find(term)
        while start != -1:
            for k in range(start, start + width):
                mark[k] = True
            start = line.find(term, start + 1)
    out = []
    i = 0
    while i < n:
        if mark[i]:
            j = i
            while j < n and mark[j]:
                j += 1
            out.append("<hi>")
            out.append(line[i:j])
            out.append("</hi>")
            i = j
        else:
            out.append(line[i])
            i += 1
    return "".join(out)

The obvious version

Stand at every letter of the line and test every term against the slice starting there, raising the flags on a hit. Then walk the flags letter by letter, opening a marker the moment a lowered flag turns raised and closing it the moment it turns back, with a final close if the line ends inside a run. Costs the line length times the terms times their lengths.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_add_bold_tag(line, terms):
    n = len(line)
    mark = [False] * n
    for i in range(n):
        for term in terms:
            width = len(term)
            if width and line[i:i + width] == term:
                for k in range(i, i + width):
                    mark[k] = True
    pieces = []
    open_now = False
    for i in range(n):
        if mark[i] and not open_now:
            pieces.append("<hi>")
            open_now = True
        elif not mark[i] and open_now:
            pieces.append("</hi>")
            open_now = False
        pieces.append(line[i])
    if open_now:
        pieces.append("</hi>")
    return "".join(pieces)

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in