616. Add Bold Tag in String - Detailed Explanation

Approach 2: Merging Intervals

Idea

1. Find All Matching Intervals:
   For each word in dict, scan s for its occurrences and record the start and end indices as intervals.

2. Merge Overlapping Intervals:
   Sort the intervals and merge them if they overlap or are consecutive. This yields a list of non-overlapping intervals that represent the bold regions.

3. Insert Bold Tags:
   Use the merged intervals to insert <b> and </b> in the appropriate positions in s.

Discussion

• Pros:
  – This approach cleanly separates finding the positions and then merging them.
• Cons:
  – It requires extra space for storing intervals and involves sorting, which is O(k log k) (where k is the number of intervals).

Complexity Analysis

• Time Complexity:

  • For Approach 1 (Boolean Array):
    • For each word, we search the string and mark positions. In the worst case (if many words are present and they occur often), this takes O(n * m) where n is the length of s and m is the number of words.
    • Building the final string is O(n).
    • Overall: Approximately O(n * m).

• Space Complexity:

  • O(n) for the boolean array and O(n) for building the result.

• For Approach 2 (Intervals):

  • The interval collection and merging also take O(n * m) time in the worst case and O(k) space for storing intervals.

Step-by-Step Walkthrough and Visual Example

Using s = "aaabbcc" and dict = ["aaa", "aab", "bc"] with the Boolean array method:

1. Initialize:

   • s = "aaabbcc"
   • bold = [false, false, false, false, false, false, false]

2. Mark Occurrences:

   • For "aaa": found at index 0 → mark indices 0, 1, 2.
     bold becomes: [true, true, true, false, false, false, false]
   • For "aab": found at index 1 → mark indices 1, 2, 3.
     bold becomes: [true, true, true, true, false, false, false]
   • For "bc": found at index 4 → mark indices 4 and 5.
     bold becomes: [true, true, true, true, true, true, false]

3. Build the Result String:

   • Iterate over s using the bold array.
   • From index 0 to 5, all positions are true, so wrap these in <b> and </b>.
   • Append the last character (index 6) normally.
   • Final result: "<b>aaabbc</b>c".

Common Mistakes and Edge Cases

Common Mistakes

• Forgetting to Merge Overlapping Regions:
  If you mark positions individually without merging, you might insert multiple nested <b> tags.

• Incorrect Interval Boundaries:
  Be careful with the start and end indices—ensure that you mark all characters that belong to a matching word.

• Handling Adjacent Bold Regions:
  Two bold regions that touch must be merged into one continuous bold region.

Edge Cases

• No Matches:
  If none of the words in dict occur in s, return s without any modifications.

• Empty String:
  If s is empty, return an empty string.

• Overlapping Matches:
  Words in dict might overlap (for example, "ab" and "bc" in "abc"), so the algorithm must correctly merge the bold regions.

Variations

• Different Tag Wrapping:
  Instead of bold tags, you may be required to wrap matching substrings with other tags or symbols.

• Case-Insensitive Matching:
  Some variations might require matching words in a case-insensitive manner.

• Multiple Patterns with Priorities:
  A more advanced variation might involve different patterns that have different formatting rules.

Related Problems for Further Practice

• Merge Intervals:
  A classic problem that involves merging overlapping intervals.

• Substring Search / Pattern Matching:
  Problems that require finding occurrences of a pattern within a text.

• Text Formatting:
  Problems that involve modifying a string by inserting markers based on certain conditions.