Find Subsequence of Length K With the Largest Sum

Problem

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.

Examples

Example 1

1
2
3
4

Input: s = "abcxyz123", words = ["abc","123"]
Output: "<b>abc</b>xyz<b>123</b>"
Explanation: The two strings of words are substrings of s as following: "abcxyz123".
We add <b> before each substring and </b> after each substring.

Example 2

1
2
3
4
5
6
7
8

Input: s = "aaabbb", words = ["aa","b"]
Output: "<b>aaabbb</b>"
Explanation: 
"aa" appears as a substring two times: "aaabbb" and "aaabbb".
"b" appears as a substring three times: "aaabbb", "aaabbb", and "aaabbb".
We add <b> before each substring and </b> after each substring: "<b>a<b>a</b>a</b><b>b</b><b>b</b><b>b</b>".
Since the first two <b>'s overlap, we merge them: "<b>aaa</b><b>b</b><b>b</b><b>b</b>".
Since now the four <b>'s are consecutive, we merge them: "<b>aaabbb</b>".

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

Method 1 – Interval Merging with Marking

Intuition

We want to bold all substrings in s that match any word in words. Overlapping or consecutive matches should be merged into a single bold region. By marking all characters that should be bolded, then merging consecutive marked regions, we can efficiently build the result.

Approach

  1. Create a boolean array bold of length s to mark which characters should be bolded.
  2. For each word in words, search for all occurrences in s and mark the corresponding indices in bold as True.
  3. Iterate through s, and whenever entering or exiting a bold region (i.e., bold[i] changes), insert <b> or </b> tags accordingly.
  4. Concatenate the result and return.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
  string addBoldTag(string s, vector<string>& words) {
    int n = s.size();
    vector<bool> bold(n, false);
    for (const string& w : words) {
      size_t pos = s.find(w, 0);
      while (pos != string::npos) {
        for (int i = pos; i < pos + w.size(); ++i) bold[i] = true;
        pos = s.find(w, pos + 1);
      }
    }
    string ans;
    for (int i = 0; i < n; ++i) {
      if (bold[i] && (i == 0 || !bold[i-1])) ans += "<b>";
      ans += s[i];
      if (bold[i] && (i == n-1 || !bold[i+1])) ans += "</b>";
    }
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func addBoldTag(s string, words []string) string {
  n := len(s)
  bold := make([]bool, n)
  for _, w := range words {
    for i := 0; i <= n-len(w); i++ {
      if s[i:i+len(w)] == w {
        for j := i; j < i+len(w); j++ {
          bold[j] = true
        }
      }
    }
  }
  var ans []byte
  for i := 0; i < n; i++ {
    if bold[i] && (i == 0 || !bold[i-1]) {
      ans = append(ans, []byte("<b>")...)
    }
    ans = append(ans, s[i])
    if bold[i] && (i == n-1 || !bold[i+1]) {
      ans = append(ans, []byte("</b>")...)
    }
  }
  return string(ans)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
  public String addBoldTag(String s, String[] words) {
    int n = s.length();
    boolean[] bold = new boolean[n];
    for (String w : words) {
      int idx = s.indexOf(w);
      while (idx != -1) {
        for (int i = idx; i < idx + w.length(); i++) bold[i] = true;
        idx = s.indexOf(w, idx + 1);
      }
    }
    StringBuilder ans = new StringBuilder();
    for (int i = 0; i < n; i++) {
      if (bold[i] && (i == 0 || !bold[i-1])) ans.append("<b>");
      ans.append(s.charAt(i));
      if (bold[i] && (i == n-1 || !bold[i+1])) ans.append("</b>");
    }
    return ans.toString();
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
  fun addBoldTag(s: String, words: Array<String>): String {
    val n = s.length
    val bold = BooleanArray(n)
    for (w in words) {
      var idx = s.indexOf(w)
      while (idx != -1) {
        for (i in idx until idx + w.length) bold[i] = true
        idx = s.indexOf(w, idx + 1)
      }
    }
    val ans = StringBuilder()
    for (i in 0 until n) {
      if (bold[i] && (i == 0 || !bold[i-1])) ans.append("<b>")
      ans.append(s[i])
      if (bold[i] && (i == n-1 || !bold[i+1])) ans.append("</b>")
    }
    return ans.toString()
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
  def addBoldTag(self, s: str, words: list[str]) -> str:
    n = len(s)
    bold = [False] * n
    for w in words:
      start = s.find(w)
      while start != -1:
        for i in range(start, start + len(w)):
          bold[i] = True
        start = s.find(w, start + 1)
    ans = []
    for i in range(n):
      if bold[i] and (i == 0 or not bold[i-1]):
        ans.append("<b>")
      ans.append(s[i])
      if bold[i] and (i == n-1 or not bold[i+1]):
        ans.append("</b>")
    return ''.join(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

impl Solution {
  pub fn add_bold_tag(s: String, words: Vec<String>) -> String {
    let n = s.len();
    let mut bold = vec![false; n];
    let s_bytes = s.as_bytes();
    for w in &words {
      let w_bytes = w.as_bytes();
      for i in 0..=n-w.len() {
        if &s_bytes[i..i+w.len()] == w_bytes {
          for j in i..i+w.len() {
            bold[j] = true;
          }
        }
      }
    }
    let mut ans = String::new();
    let s_chars: Vec<char> = s.chars().collect();
    for i in 0..n {
      if bold[i] && (i == 0 || !bold[i-1]) {
        ans.push_str("<b>");
      }
      ans.push(s_chars[i]);
      if bold[i] && (i == n-1 || !bold[i+1]) {
        ans.push_str("</b>");
      }
    }
    ans
  }
}

Complexity

  • ⏰ Time complexity: O(n * m * k) where n is the length of s, m is the number of words, and k is the average length of words (since for each word, we scan s for all occurrences).
  • 🧺 Space complexity: O(n) for the bold array and output string.