Add Bold Tag in String - Practice Coding Problems

Add Bold Tag in String - Problem

You are given a string s and an array of strings words. You should add a closed pair of bold tag  and  to wrap the substrings in s that exist in words.

Rules for bold tagging:

If two such substrings overlap, you should wrap them together with only one pair of bold tags
If two substrings wrapped by bold tags are consecutive, you should combine them

Return s after adding the bold tags.

Input & Output

Example 1 — Basic Case

$ Input: s = "abcxyz123", words = ["abc", "123"]

› Output: "abcxyz123"

💡 Note: "abc" appears at start (positions 0-2) and "123" appears at end (positions 6-8). Both are wrapped with bold tags separately since they don't overlap.

Example 2 — Overlapping Words

$ Input: s = "aaabbcc", words = ["aaa", "aab", "bc"]

› Output: "aaabbcc"

💡 Note: "aaa" matches at 0-2, "aab" matches at 1-3, "bc" matches at 4-5. Since positions 0-5 are all marked bold and consecutive, they merge into one bold tag.

Example 3 — No Matches

$ Input: s = "hello", words = ["world", "test"]

› Output: "hello"

💡 Note: None of the words appear in the string, so no bold tags are added.

Constraints

1 ≤ s.length ≤ 1000
0 ≤ words.length ≤ 100
1 ≤ words[i].length ≤ 100
s and words[i] consist of English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

Original string and array of words to highlight

Find Matches

Locate all occurrences of words in the string

Add Tags

Wrap matching substrings with bold tags, merging overlaps

Key Takeaway

🎯 Key Insight: Mark character positions first, then merge consecutive bold regions to handle overlaps automatically

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to first mark all character positions that should be bold, then merge consecutive regions when building the output. Best approach uses HashSet for O(1) word lookup combined with substring checking. Time: O(n × L²), Space: O(W × L + n).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with HashSet	O(n × L²)	O(W × L + n)	Use HashSet for faster word lookup and merge overlapping intervals
Brute Force String Matching	O(n × m × k)	O(n)	Check every position in string for every word, mark bold positions

Optimized with HashSet — Algorithm Steps

Store words in HashSet for fast lookup
For each position, check all substring lengths
Mark positions that match any word
Merge consecutive bold regions when building output

Visualization

Tap to expand

Step-by-Step Walkthrough

HashSet

Store words for O(1) lookup

Substring Check

Check all substrings at each position

Merge Ranges

Combine consecutive bold positions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    char** words;
    int size;
} WordSet;

bool containsWord(WordSet* set, char* word) {
    for (int i = 0; i < set->size; i++) {
        if (strcmp(set->words[i], word) == 0) {
            return true;
        }
    }
    return false;
}

char* solution(char* s, char** words, int wordsSize) {
    if (wordsSize == 0 || strlen(s) == 0) {
        char* result = (char*)malloc(strlen(s) + 1);
        strcpy(result, s);
        return result;
    }
    
    WordSet wordSet = {words, wordsSize};
    int maxLen = 0;
    for (int i = 0; i < wordsSize; i++) {
        int len = strlen(words[i]);
        if (len > maxLen) maxLen = len;
    }
    
    int n = strlen(s);
    bool* bold = (bool*)calloc(n, sizeof(bool));
    
    // Mark all positions that should be bold
    char* temp = (char*)malloc(maxLen + 1);
    for (int i = 0; i < n; i++) {
        int end = (i + maxLen < n) ? i + maxLen : n;
        for (int j = i + 1; j <= end; j++) {
            strncpy(temp, s + i, j - i);
            temp[j - i] = '\0';
            if (containsWord(&wordSet, temp)) {
                for (int k = i; k < j; k++) {
                    bold[k] = true;
                }
            }
        }
    }
    
    // Build result string with bold tags
    char* result = (char*)malloc(3 * n + 100);
    int pos = 0;
    int i = 0;
    
    while (i < n) {
        if (bold[i]) {
            strcpy(result + pos, "<b>");
            pos += 3;
            while (i < n && bold[i]) {
                result[pos++] = s[i++];
            }
            strcpy(result + pos, "</b>");
            pos += 4;
        } else {
            result[pos++] = s[i++];
        }
    }
    result[pos] = '\0';
    
    free(bold);
    free(temp);
    return result;
}

int main() {
    char s[1000];
    char words_input[1000];
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    fgets(words_input, sizeof(words_input), stdin);
    words_input[strcspn(words_input, "\n")] = 0;
    
    char** words = (char**)malloc(100 * sizeof(char*));
    int wordsSize = 0;
    char* token = strtok(words_input + 1, ",\"[]");
    while (token != NULL) {
        words[wordsSize] = (char*)malloc(strlen(token) + 1);
        strcpy(words[wordsSize], token);
        wordsSize++;
        token = strtok(NULL, ",\"[]");
    }
    
    char* result = solution(s, words, wordsSize);
    printf("%s\n", result);
    
    free(result);
    for (int i = 0; i < wordsSize; i++) {
        free(words[i]);
    }
    free(words);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × L²)

For each position (n), check substrings up to max word length L, HashSet lookup is O(L)

✓ Linear Growth

Space Complexity

O(W × L + n)

HashSet stores all words (W×L characters) plus boolean array (n)

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with HashSet — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler