⚡Flashcard Drill➔
NeetCode #831LC-616MediumIntervalsNC Algo100
← Back to All Problems

#831 · #616 · Add Bold Tag in String(给字符串添加加粗标签)

📌 Problem Statement & Constraints

You are given a string s and a list of words. Wrap in <b> and </b> every substring of s that matches any word, merging overlapping or adjacent matches into a single bold region. Return the resulting string. Constraints: 1 <= s.length <= 1000, 0 <= words.length <= 100, 1 <= words[i].length <= s.length, s and words[i] consist of lowercase English letters.

💡 Core Algorithmic Approaches

  1. Every occurrence of every word defines an interval [start, start + len - 1] over the indices of s.
  2. Mark a boolean array over the string for every covered index; overlapping and adjacent matches then merge automatically into maximal runs of marked positions.
  3. Scan the string and wrap each maximal run of marked indices with the bold tags.
  4. Merging the intervals before emitting is what prevents nested or duplicated tags.

💻 Benchmark Python3 Implementation

class Solution:
    def addBoldTag(self, s: str, words: List[str]) -> str:
        n = len(s)
        bold = [False] * n
        for w in words:
            start = s.find(w)
            while start != -1:
                for i in range(start, start + len(w)):
                    bold[i] = True          # mark this occurrence
                start = s.find(w, start + 1)   # allow overlapping occurrences
        res = []
        i = 0
        while i < n:
            if bold[i]:
                res.append("<b>")
                while i < n and bold[i]:    # maximal run of marked indices
                    res.append(s[i])
                    i += 1
                res.append("</b>")
            else:
                res.append(s[i])
                i += 1
        return "".join(res)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(W * n) in the worst case, where W is the number of words: each find scan plus marking.
💾 Space Complexity
O(n) for the mark array and the output.

⚠️ Interview Pitfalls & Follow-ups

  • Advancing the search by len(w): overlapping occurrences (like aa in aaa) require advancing by one, so the next find starts at start + 1.
  • Emitting a tag per occurrence: overlapping matches must merge into one region, which the mark array guarantees.
  • Using str.replace: a naive replace cannot merge overlaps or adjacent matches and would nest tags incorrectly.
  • Forgetting that adjacent matches merge: ab and bc in abc cover every index, so a single bold region is correct.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Intervals Problems