# 616. Add Bold Tag in String

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*.

**Example 1:**

```
Input: s = "abcxyz123", words = ["abc","123"]
Output: "<b>abc</b>xyz<b>123</b>"
```

**Example 2:**

```
Input: s = "aaabbcc", words = ["aaa","aab","bc"]
Output: "<b>aaabbc</b>c"
```

**Constraints:**

* `1 <= s.length <= 1000`
* `0 <= words.length <= 100`
* `1 <= words[i].length <= 1000`
* `s` and `words[i]` consist of English letters and digits.
* All the values of `words` are **unique**.

## Solution

The first idea is to arrange the range that shall be bold.

It will be similar to an interval merge problem. My personal preference is to use a treeMap.

Using floorKey to get the prevStart of the interval and the nextStart of the next interval.

With some merge operations, we can have a treeMap to record all the ranges.

And we iterate the original string and append \<b> (in the start of interval ) or \</b> (in the end of interval)\
accordingly.

```java
    public String addBoldTag(String s, String[] words) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int i = 0; i < s.length(); i++){
            for(String word : words) {
                if(s.substring(i).startsWith(word)) {
                    update(map, i, i + word.length()-1);
                }
            }    
        }
        
        StringBuilder ret = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            if(map.keySet().contains(i)){
                ret.append("<b>");
            }
            ret.append(s.charAt(i));
            if(map.values().contains(i)){
                ret.append("</b>");
            }
            
        }     
        return ret.toString();
    }
    
    public void update(TreeMap<Integer, Integer> map, int start, int end) {
        Integer prevStart = map.floorKey(start);
        int prevEnd = prevStart == null ? -1 : map.get(prevStart);
        Integer nextStart = map.floorKey(end);
        int nextEnd = nextStart == null ? -1 : map.get(nextStart);
        
        if(start != 0 && prevEnd >= (start-1)){
            start = prevStart;
        }
        if(nextEnd > end){
            end = nextEnd;
        }
        
        map.put(start, end);
        map.subMap(start, false, end, true).clear();
    }

```
