Solution For Add Bold Tag In String
Problem statement:
Given a string s and an integer array startIndices of the same length.
The task is to concatenate all substrings in s which start at indices specified in startIndices, sorted in ascending order, and wrap them with bold tag and .
If two substrings overlap, you should wrap them together by only one pair of bold tags. If two consecutive substrings are separated by more than one character, you should place the bold tags separately.
Return the final string after the aforementioned operations.
Example 1:
Input: s = “abcxyz123”, startIndices = [0, 6],
Output: “abcxyz123″
Explanation:
– substrings starting at index 0: “abcxyz”
– substrings starting at index 6: “123”
– concatenate substrings “abcxyz” and “123” together and wrap them with bold tag
“” and ““.
Example 2:
Input: s = “aaabbcc”, startIndices = [0, 1, 4, 5],
Output: “aaabbcc”
Explanation:
– substrings starting at index 0: “aaa”
– substrings starting at index 1: “aa”
– substrings starting at index 4: “bcc”
– substrings starting at index 5: “c”
– concatenate substrings “aaab” and “cc” together and wrap them with bold tag
“” and ““.
Constraints:
1 <= s.length <= 1000
0 <= startIndices.length <= 100
0 <= startIndices[i] <= s.length – 1
startIndices are distinct.
Approach:
This problem can be solved using string manipulation and concept of merging overlapped or adjacent substrings. We will start iterating over the startIndices array and extract the substring from the given string s starting from the current index i up to the index mentioned in the startIndices array.
While extracting the substrings, we need to merge the adjacent substrings if they overlap or are separated by only one character. While doing so, we need to keep track of the starting and ending indices of the merged substrings in order to enclose them with the bold tag and .
For this, we can initialize a variable bold to an array of booleans of length equal to the size of the given string. Loop through the startIndices array and mark the corresponding positions in the bold array as true. Then loop through the bold array and merge all the contiguous true values into one substring. We will then add the bold tag to these substrings and store them in a list.
We will then concatenate all the substrings stored in the list to get the final string after applying the above operations.
Algorithm:
1. Initialize an empty list boldSubstrings to store the bold substrings.
2. Initialize a boolean array bold to mark the positions of the bold substrings and initialize all its values to false.
3. Loop through the startIndices array and mark the corresponding positions in the bold array as true.
4. Initialize variables startIndex and endIndex to -1 for keeping track of the start and end positions of the merged substrings.
5. Loop through the bold array and merge all the contiguous true values into one substring.
6. If the current value of bold[i] is true and the startIndex is -1, then set the startIndex to i.
7. If the current value of bold[i] is false and startIndex is not -1, then set the endIndex to i-1 and add the bold tag to the substring starting from startIndex to endIndex. Add this substring to the list boldSubstrings and set the startIndex to -1.
8. If there are any remaining true values in the bold array, then set the endIndex to the last index of the string and add the bold tag to the substring starting from startIndex to endIndex. Add this substring to the list boldSubstrings.
9. Return the final string obtained by joining all the substrings in the list using the Python join() method.
Python Code:
def addBoldTag(s, startIndices):
n = len(s)
bold = [False] * n
for startIndex in startIndices:
bold[startIndex] = True
boldSubstrings = []
startIndex, endIndex = -1, -1
for i in range(n):
if bold[i] and startIndex == -1:
startIndex = i
if not bold[i] and startIndex != -1:
endIndex = i-1
boldSubstrings.append("<b>" + s[startIndex:endIndex+1] + "</b>")
startIndex = -1
if startIndex != -1:
endIndex = len(s)-1
boldSubstrings.append("<b>" + s[startIndex:endIndex+1] + "</b>")
return "".join(boldSubstrings)
Testing the code with the given test cases
print(addBoldTag(“abcxyz123″, [0, 6])) #”abcxyz123″
print(addBoldTag(“aaabbcc”, [0, 1, 4, 5])) #”aaabbcc“
Step by Step Implementation For Add Bold Tag In String
/**
* Given a string s and a list of strings dict, you need to add a closed pair of bold tag and to wrap the substrings in s that exist in dict. If two such substrings overlap, you need to wrap them together by only one pair of closed bold tag. Also, if two substrings wrapped by bold tags are consecutive, you need to combine them.
*
* Example 1:
* Input:
* s = "abcxyz123"
* dict = ["abc","123"]
* Output:
* "abcxyz123"
*
* Example 2:
* Input:
* s = "aaabbcc"
* dict = ["aaa","aab","bc"]
* Output:
* "aaabbcc"
*
* Note:
* The given dict won't contain duplicates, and its length won't exceed 100.
* All the strings in input have length in range [1, 1000].
*/
// Solution:
// We can solve this problem by keeping track of the start and end indices of the substrings in the dictionary that appear in the string.
// We first initialize two arrays, start and end, of the same length as the string. Start tracks the starting index of the substring, while end tracks the ending index.
// We then iterate through the string, and for each character, we check if it is the start of a substring in the dictionary. If it is, we update the start array accordingly.
// We also check if it is the end of a substring in the dictionary. If it is, we update the end array accordingly.
// After we have iterated through the entire string, we can then go through the start and end arrays to construct the final string.
class Solution {
public String addBoldTag(String s, String[] dict) {
boolean[] bold = new boolean[s.length()];
int end = -1;
for (int i = 0; i < s.length(); i++) {
for (String word : dict) {
if (s.startsWith(word, i)) {
end = Math.max(end, i + word.length() - 1);
}
}
bold[i] = end >= i;
}
StringBuilder result = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (!bold[i]) {
result.append(s.charAt(i));
continue;
}
int j = i;
while (j < s.length() && bold[j]) j++;
result.append("" + s.substring(i, j) + "");
i = j - 1;
}
return result.toString();
}
}def addBoldTag(self, s, dict):
n = len(s)
bold = [False] * (n+1)
for i in xrange(n):
for j in dict:
if s[i:i+len(j)] == j:
bold[i] = True
bold[i+len(j)] = True
res = ''
for i in xrange(n):
if bold[i] and not bold[i-1]:
res += ''
res += s[i]
if bold[i] and not bold[i+1]:
res += ''
return resvar addBoldTag = function(s, dict) {
// create an array to store the indices of the characters in the string that should be bold
let boldIndices = [];
// iterate through the dict
for (let i = 0; i < dict.length; i++) {
// get the index of the first appearance of the word in the string
let index = s.indexOf(dict[i]);
// continue iterating through the string until the word is no longer found
while (index !== -1) {
// push the index of the first character of the word into the boldIndices array
boldIndices.push(index);
// get the index of the next appearance of the word in the string
index = s.indexOf(dict[i], index + 1);
}
}
// sort the boldIndices array in ascending order
boldIndices.sort((a, b) => a - b);
// create a variable to store the bolded string
let bolded = "";
// iterate through the boldIndices array
for (let i = 0; i < boldIndices.length; i++) {
// if this is the first index in the array, add an opening bold tag before it
if (i === 0) {
bolded += "";
}
// if this is not the first index in the array, and the difference between this index and the previous index is greater than 1,
// add an opening bold tag before this index
else if (boldIndices[i] - boldIndices[i-1] > 1) {
bolded += "";
}
// add the character at this index to the bolded string
bolded += s[boldIndices[i]];
// if this is the last index in the array, add a closing bold tag after it
if (i === boldIndices.length - 1) {
bolded += "";
}
}
// return the bolded string
return bolded;
};class Solution {
public:
string addBoldTag(string s, vector& dict) {
int n = s.size();
vector bold(n, false);
int end = 0;
for (int i = 0; i < n; i++) {
for (string word : dict) {
int len = word.size();
if (i + len <= n && word == s.substr(i, len)) {
bold[i] = true;
end = max(end, i + len);
}
}
}
string res;
for (int i = 0; i < n; i++) {
if (!bold[i]) {
res += s[i];
continue;
}
int j = i;
while (j < end) {
if (bold[j]) j++;
else break;
}
res += "" + s.substr(i, j - i) + "";
i = j - 1;
}
return res;
}
}; public string AddBoldTag(string s, IListdict) { //edge case if (s == null || s.Length == 0) return ""; //create a boolean array to track which indices should be bolded bool[] bold = new bool[s.Length]; //iterate through the dictionary and mark the indices of the characters that should be bolded foreach (string word in dict) { int index = s.IndexOf(word); while (index != -1) { //mark the start and end indices of the word as true for (int i = index; i < index + word.Length; i++) { bold[i] = true; } //search for the next index of the word index = s.IndexOf(word, index + 1); } } //iterate through the boolean array and bold the appropriate indices string result = ""; for (int i = 0; i < s.Length; i++) { //if the current index should be bolded, add an opening bold tag if (bold[i] && (i == 0 || !bold[i-1])) { result += ""; } //add the current character to the result string result += s[i]; //if the current index should be bolded, add a closing bold tag if (bold[i] && (i == s.Length - 1 || !bold[i+1])) { result += ""; } } return result; }