<pre class="shiki github-dark shaku"><code>/** * @param {string} html * @param {string[]} keywords *//*Time complexity: O(n*log(n)) --&gt; Sorting time is the dominant term.m: size of tag arrayn: number of characters in stringSpace complexity: O(n+m) --&gt; Creating new array to store tags with indices + array to mutate.*/function highlightKeywords(html, keywords) { // your code here const keyLocations = []; for (let key of keywords) { const idx = html.indexOf(key); if (idx !== -1) { keyLocations.push({ str: key, start: idx, end: idx + key.length }) } } // Sort it based on end indexes keyLocations.sort((a, b) =&gt; a.end - b.end); // Merge the inclusive indexes for(let i = 0; i &lt; keyLocations.length; i++){ if(i+1 &lt; keyLocations.length &amp;&amp; keyLocations[i].end &gt;= keyLocations[i+1].start){ // Find common substring &amp; merge them const startIdx = Math.min(keyLocations[i].start, keyLocations[i+1].start); const endIdx = Math.max(keyLocations[i].end, keyLocations[i+1].end); const mergedObj = { str: html.slice(startIdx, endIdx), start: startIdx, end: endIdx, } keyLocations.splice(i, 2, mergedObj); i--; } } // Array mutation is easier const arr = html.split(""); // Start from the back so that indexes remains the same for(let i = keyLocations.length - 1; i &gt;= 0; i--){ const obj = keyLocations[i]; arr.splice(obj.end, 0, '&lt;/em&gt;'); arr.splice(obj.start, 0, '&lt;em&gt;'); } return arr.join("");};</code></pre>

Simple iterative solution - O(n*log(n)) runtime

Suppose you are implementing an auto-complete in search input. When keywords are typed, you need to highlight the keywords, how would you do that? To …