Embolden - Google Top Interview Questions

                        Solution in C++ :

string solve(string text, vector<string>& patterns) {
    vector<vector<int>> intervals;
    int N = text.size();
    for (int i = 0; i < N; i++) {
        for (auto& p : patterns) {
            if (p.size() <= N - i && text.compare(i, p.size(), p) == 0) {
                if (intervals.empty()) {
                    intervals.push_back({i, i + p.size() - 1});
                } else {
                    if (intervals.back()[1] >= i - 1)
                        intervals.back()[1] = i + p.size() - 1;
                    else
                        intervals.push_back({i, i + p.size() - 1});
                }
            }
        }
    }

    string ans;
    int idx = 0;
    for (int i = 0; i < intervals.size(); i++) {
        ans.append(text.substr(idx, intervals[i][0] - idx));
        ans.append("<b>");
        ans.append(text.substr(intervals[i][0], intervals[i][1] - intervals[i][0] + 1));
        ans.append("</b>");
        idx = intervals[i][1] + 1;
    }
    if (idx < text.size()) {
        ans.append(text.substr(idx));
    }
    return ans;
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, text, patterns):
        n = len(text)
        bolded = [False] * n

        for pat in patterns:
            start = text.find(pat)

            while start != -1:
                for i in range(start, start + len(pat)):
                    bolded[i] = True

                start = text.find(pat, start + 1)

        ans = []
        idx = 0

        while idx < n:
            if bolded[idx]:
                ans.append("<b>")

                while idx < n and bolded[idx]:
                    ans.append(text[idx])
                    idx += 1

                ans.append("</b>")
            else:
                ans.append(text[idx])
                idx += 1

        return "".join(ans)