616

class Solution {
public:
    string addBoldTag(string s, vector<string>& dict) {
        // Step1: get the raw intervals
        set<pair<int, int>> interval_raw;
        for(string d : dict){
            int i = 0;
            while(s.find(d, i) != string::npos){
                i = s.find(d, i);
                interval_raw.insert({i, i + d.length() - 1});
                i++;
            }
        }
         // Step2: get the refined intervals by merging
        vector<pair<int, int>> interval;
        for(auto item : interval_raw){
            int n = interval.size();
            if(n > 0 && item.first <= interval[n-1].second + 1)
                interval[n-1].second = max(interval[n-1].second, item.second);
            else interval.push_back(item);
        }

        // Step3: insert tags based on refined intervals
        string res(s);
        for(int i = 0; i < interval.size(); i++){
            res.insert(interval[i].first + 7 * i, "<b>");
            res.insert(interval[i].second + 7 * i + 4, "</b>");
        }
        return res;
    }
};