Add Bold Tag in String
MediumUpdated: Jul 23, 2025
Problem
You are given a string s and an array of strings words.
You should add a closed pair of bold tag <b> and </b> to wrap the substrings in s that exist in words.
- If two such substrings overlap, you should wrap them together with only one pair of closed bold-tag.
- If two substrings wrapped by bold tags are consecutive, you should combine them.
Return s after adding the bold tags.
OR as stated in duplicate "Bold words in String (Leetcode 758)":
Given an array of keywords words and a string s, make all appearances of all keywords words[i] in s bold. Any letters between <b> and </b> tags become bold.
Return s after adding the bold tags. The returned string should use the least number of tags possible, and the tags should form a valid combination.
Examples
Example 1
Input: s = "abcxyz123", words = ["abc","123"]
Output: "<b>abc</b>xyz<b>123</b>"
Explanation: The two strings of words are substrings of s as following: "abcxyz123".
We add <b> before each substring and </b> after each substring.
Example 2
Input: s = "aaabbb", words = ["aa","b"]
Output: "<b>aaabbb</b>"
Explanation:
"aa" appears as a substring two times: "aaabbb" and "aaabbb".
"b" appears as a substring three times: "aaabbb", "aaabbb", and "aaabbb".
We add <b> before each substring and </b> after each substring: "<b>a<b>a</b>a</b><b>b</b><b>b</b><b>b</b>".
Since the first two <b>'s overlap, we merge them: "<b>aaa</b><b>b</b><b>b</b><b>b</b>".
Since now the four <b>'s are consecutive, we merge them: "<b>aaabbb</b>".
Constraints
1 <= s.length <= 10000 <= words.length <= 1001 <= words[i].length <= 1000sandwords[i]consist of English letters and digits.- All the values of
wordsare unique.
Note
- This problem and Leetcode 758. Bold words in string are same. Signature in the duplicate problem is a bit different:
class Solution {
public String boldWords(String[] words, String s) {
}
}
Solution
Method 1 – Interval Merging with Marking
Intuition
We want to bold all substrings in s that match any word in words. Overlapping or consecutive matches should be merged into a single bold region. By marking all characters that should be bolded, then merging consecutive marked regions, we can efficiently build the result.
Approach
- Create a boolean array
boldof lengthsto mark which characters should be bolded. - For each word in
words, search for all occurrences insand mark the corresponding indices inboldasTrue. - Iterate through
s, and whenever entering or exiting a bold region (i.e.,bold[i]changes), insert<b>or</b>tags accordingly. - Concatenate the result and return.
Code
C++
class Solution {
public:
string addBoldTag(string s, vector<string>& words) {
int n = s.size();
vector<bool> bold(n, false);
for (const string& w : words) {
size_t pos = s.find(w, 0);
while (pos != string::npos) {
for (int i = pos; i < pos + w.size(); ++i) bold[i] = true;
pos = s.find(w, pos + 1);
}
}
string ans;
for (int i = 0; i < n; ++i) {
if (bold[i] && (i == 0 || !bold[i-1])) ans += "<b>";
ans += s[i];
if (bold[i] && (i == n-1 || !bold[i+1])) ans += "</b>";
}
return ans;
}
};
Go
func addBoldTag(s string, words []string) string {
n := len(s)
bold := make([]bool, n)
for _, w := range words {
for i := 0; i <= n-len(w); i++ {
if s[i:i+len(w)] == w {
for j := i; j < i+len(w); j++ {
bold[j] = true
}
}
}
}
var ans []byte
for i := 0; i < n; i++ {
if bold[i] && (i == 0 || !bold[i-1]) {
ans = append(ans, []byte("<b>")...)
}
ans = append(ans, s[i])
if bold[i] && (i == n-1 || !bold[i+1]) {
ans = append(ans, []byte("</b>")...)
}
}
return string(ans)
}
Java
class Solution {
public String addBoldTag(String s, String[] words) {
int n = s.length();
boolean[] bold = new boolean[n];
for (String w : words) {
int idx = s.indexOf(w);
while (idx != -1) {
for (int i = idx; i < idx + w.length(); i++) bold[i] = true;
idx = s.indexOf(w, idx + 1);
}
}
StringBuilder ans = new StringBuilder();
for (int i = 0; i < n; i++) {
if (bold[i] && (i == 0 || !bold[i-1])) ans.append("<b>");
ans.append(s.charAt(i));
if (bold[i] && (i == n-1 || !bold[i+1])) ans.append("</b>");
}
return ans.toString();
}
}
Kotlin
class Solution {
fun addBoldTag(s: String, words: Array<String>): String {
val n = s.length
val bold = BooleanArray(n)
for (w in words) {
var idx = s.indexOf(w)
while (idx != -1) {
for (i in idx until idx + w.length) bold[i] = true
idx = s.indexOf(w, idx + 1)
}
}
val ans = StringBuilder()
for (i in 0 until n) {
if (bold[i] && (i == 0 || !bold[i-1])) ans.append("<b>")
ans.append(s[i])
if (bold[i] && (i == n-1 || !bold[i+1])) ans.append("</b>")
}
return ans.toString()
}
}
Python
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
start = s.find(w, start + 1)
ans = []
for i in range(n):
if bold[i] and (i == 0 or not bold[i-1]):
ans.append("<b>")
ans.append(s[i])
if bold[i] and (i == n-1 or not bold[i+1]):
ans.append("</b>")
return ''.join(ans)
Rust
impl Solution {
pub fn add_bold_tag(s: String, words: Vec<String>) -> String {
let n = s.len();
let mut bold = vec![false; n];
let s_bytes = s.as_bytes();
for w in &words {
let w_bytes = w.as_bytes();
for i in 0..=n-w.len() {
if &s_bytes[i..i+w.len()] == w_bytes {
for j in i..i+w.len() {
bold[j] = true;
}
}
}
}
let mut ans = String::new();
let s_chars: Vec<char> = s.chars().collect();
for i in 0..n {
if bold[i] && (i == 0 || !bold[i-1]) {
ans.push_str("<b>");
}
ans.push(s_chars[i]);
if bold[i] && (i == n-1 || !bold[i+1]) {
ans.push_str("</b>");
}
}
ans
}
}
Complexity
- ⏰ Time complexity:
O(n * m * k)wherenis the length ofs,mis the number of words, andkis the average length of words (since for each word, we scansfor all occurrences). - 🧺 Space complexity:
O(n)for theboldarray and output string.