Bold Words in String

medium strings intervals trie

Problem

Given a list of words and a string s, surround in tags any substring of s that matches a word. Overlapping or adjacent bold segments merge into one.

Inputwords=['ab','bc'], s='aabcd'

Output'aabcd'

Positions 1-3 are covered by 'ab' and 'bc' overlapping.

input

def boldWords(words, s):
    n = len(s)
    mask = [False]*n
    for w in words:
        i = s.find(w)
        while i != -1:
            for j in range(i, i+len(w)): mask[j] = True
            i = s.find(w, i+1)
    out = []
    i = 0
    while i < n:
        if mask[i]:
            j = i
            while j < n and mask[j]: j += 1
            out.append("<b>" + s[i:j] + "</b>")
            i = j
        else:
            out.append(s[i]); i += 1
    return "".join(out)

function boldWords(words, s) {
  const n = s.length, mask = new Array(n).fill(false);
  for (const w of words) {
    let i = s.indexOf(w);
    while (i !== -1) {
      for (let j = i; j < i+w.length; j++) mask[j] = true;
      i = s.indexOf(w, i+1);
    }
  }
  let out = "", i = 0;
  while (i < n) {
    if (mask[i]) {
      let j = i;
      while (j < n && mask[j]) j++;
      out += "<b>" + s.slice(i,j) + "</b>"; i = j;
    } else { out += s[i++]; }
  }
  return out;
}

String boldWords(String[] words, String s) {
    int n = s.length();
    boolean[] mask = new boolean[n];
    for (String w : words) {
        int i = s.indexOf(w);
        while (i != -1) {
            for (int j = i; j < i+w.length(); j++) mask[j] = true;
            i = s.indexOf(w, i+1);
        }
    }
    StringBuilder out = new StringBuilder();
    int i = 0;
    while (i < n) {
        if (mask[i]) {
            int j = i;
            while (j < n && mask[j]) j++;
            out.append("<b>").append(s, i, j).append("</b>"); i = j;
        } else out.append(s.charAt(i++));
    }
    return out.toString();
}

string boldWords(vector<string>& words, string s) {
    int n = s.size();
    vector<bool> mask(n, false);
    for (auto& w : words) {
        size_t i = s.find(w);
        while (i != string::npos) {
            for (size_t j = i; j < i+w.size(); j++) mask[j] = true;
            i = s.find(w, i+1);
        }
    }
    string out; int i = 0;
    while (i < n) {
        if (mask[i]) {
            int j = i;
            while (j < n && mask[j]) j++;
            out += "<b>" + s.substr(i, j-i) + "</b>"; i = j;
        } else out += s[i++];
    }
    return out;
}

Explanation

The tricky part of this problem is that bold words can overlap or sit right next to each other, and when they do they should merge into one set of  tags. Trying to insert tags directly while scanning gets messy fast.

The clean trick is to separate marking from printing. First we build a boolean array called mask, one slot per character of s, all starting as false. For every word we find every place it occurs in s and set those positions to true.

After marking, mask tells us exactly which characters should be bold, and overlaps simply set the same slots true again — no special handling needed.

The second pass walks through s. Whenever we hit a true slot, we extend forward over the whole run of true values and wrap that entire chunk in one pair of tags. Plain (false) characters are copied as-is.

Example: words=['ab','bc'], s='aabcd'. Positions 1, 2, 3 get marked true (1-2 by 'ab', 2-3 by 'bc'). The run 1..3 is the substring abc, giving aabcd.

Time: O(n*S) Space: O(n)