616. Add Bold Tag in String - Detailed Explanation

Problem Statement

Description:
Given a string s and an array of strings dict, add a pair of bold tags <b> and </b> to wrap substrings in s that match any string in dict. If two such substrings overlap or are consecutive, you must merge them into one continuous bold section.

Examples:

• Example 1:
  Input:

  s = "abcxyz123"
  dict = ["abc", "123"]
  

  Output:

  "<b>abc</b>xyz<b>123</b>"
  

  Explanation:
  The substring "abc" (indices 0-2) and "123" (indices 6-8) are found in the dictionary. They are separately bolded since there is no overlap.

• Example 2:
  Input:

  s = "aaabbcc"
  dict = ["aaa", "aab", "bc"]
  

  Output:

  "<b>aaabbc</b>c"
  

  Explanation:
  "aaa" and "aab" match overlapping regions, and "bc" matches part of the string immediately after. The intervals merge into one bold section covering indices 0–5.

• Example 3:
  Input:

  s = "abcdef"
  dict = ["gh", "ij"]
  

  Output:

  "abcdef"
  

  Explanation:
  None of the words in the dictionary appear in s, so no bold tags are added.

Constraints:

• 1 ≤ s.length ≤ 1000
• 1 ≤ dict.length ≤ 100
• 1 ≤ dict[i].length ≤ 100
• s and dict[i] consist of lowercase English letters.

Hints Before Diving into the Solution

• Hint 1:
  Think about using an auxiliary array (or list) of booleans to mark which indices in s should be wrapped in bold tags. For each dictionary word, mark all positions that are part of a match.

• Hint 2:
  After marking the indices, consider how you can merge consecutive or overlapping marked intervals. How would you know where one bold section starts and ends?

Approach 1: Brute Force / Marking Method

Idea:

1. Marking the Bold Positions:
   Create an array bold of the same length as s and initialize all values to False.
   For each word in dict, scan s and mark indices as True if they belong to a matching substring.

2. Merging Intervals:
   Traverse the bold array. When you encounter a True value that starts a sequence (or continues from a previous bold region), mark the start index. When you hit a False after a series of True values, mark the end index of that bold section. Insert <b> before the start and </b> after the end.

Detailed Steps:

• Step 1:
  For each word in dict, iterate through s using a sliding window to check if s[i:i+len(word)] equals the word. If yes, mark all positions from i to i+len(word)-1 as True in bold.

• Step 2:
  Iterate through bold and whenever you see a transition from False to True, insert a <b> tag. When transitioning from True to False, insert a </b> tag.

Visual Example (Using Example 1):

• s: "a b c x y z 1 2 3"
• Indices: 0 1 2 3 4 5 6 7 8
• Marking "abc": Mark indices 0, 1, 2 as True.
• Marking "123": Mark indices 6, 7, 8 as True.
• Bold Array: [T, T, T, F, F, F, T, T, T]
• Insert Tags:
  • Start bold at index 0, end at index 2 → wrap "abc"
  • Start bold at index 6, end at index 8 → wrap "123"

Approach 2: Using Interval Merging

Idea:

1. Finding Intervals:
   Instead of marking every index, find the start and end indices for each matching substring and store them as intervals.

2. Merge Overlapping Intervals:
   Sort the intervals by their start index. Merge intervals if they overlap or are consecutive.

3. Build the Final String:
   Use the merged intervals to add <b> and </b> tags to the corresponding substrings in s.

Detailed Steps:

• Step 1:
  For each word in dict, iterate over s and find intervals [i, j] where s[i:j] matches the word.

• Step 2:
  Sort the intervals and merge any intervals that overlap or touch.

• Step 3:
  Build the resulting string by iterating over s and inserting tags at the boundaries defined by the merged intervals.

Visual Example (Using Example 2):

• s: "aaabbcc"
• Intervals Found:
  • For "aaa": [0, 2]
  • For "aab": [1, 3]
  • For "bc": [4, 5]
• Merge Intervals:
  • [0, 2] and [1, 3] merge to [0, 3]
  • [0, 3] and [4, 5] are consecutive (if adjacent characters are to be merged) or may be merged based on problem specifics (in this example, they merge into [0, 5]).
• Insert Tags:
  Wrap indices 0–5 with <b> and </b>, then append the rest of the string.

Python Code