Given a string str and an array of indices chars[] that describes the indices in the original string where the characters will be added. For this post, let the character to be inserted in star (*). Each star should be inserted before the character at the given index. Return the modified string after the stars have been added.
Examples:
Input: str = “neveropen”, chars = [1, 5, 7, 9]
Output: g*eeks*fo*rg*eeks
Explanation: The indices 1, 5, 7, and 9 correspond to the bold characters in “geeksforneveropen”.Input: str = “spacing”, chars = [0, 1, 2, 3, 4, 5, 6]
Output: “*s*p*a*c*i*n*g”
Approach: To solve the problem follow the below idea:
Iterate over the string and keep track of the count of the characters in the string so far and whenever your count becomes equal to the element in the array of stars, append a star to the resultant string and move ahead in your star array.
Follow the steps mentioned below to implement the idea:
- Create a string ans for storing your resultant string.
- Take one pointer j initially as 0.
- Iterate over the string and whenever your index that represents the count of characters becomes equal to the element in stars[j], append the star in your ans string and move the j pointer ahead.
- Also, at each move, append the current character in your string ans.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to add starsstring addStars(string s, vector<int>& stars){ // Create a string ans for storing // resultant string string ans = ""; int j = 0; for (int i = 0; i < s.length(); i++) { // If the count of characters // become equal to the stars[j], // append star if (j < stars.size() && i == stars[j]) { ans += '*'; j++; } ans += s[i]; } return ans;}// Driver codeint main(){ string str = "neveropen"; vector<int> chars = { 1, 5, 7, 9 }; string ans = addStars(str, chars); // Printing the resultant string cout << ans << endl;} |
Java
// Java code to implement the approachimport java.io.*;class GFG{ // Function to add stars public static String addStars(String s, int stars[]) { // Create a string ans for storing // resultant string String ans = ""; int j = 0; for (int i = 0; i < s.length(); i++) { // If the count of characters // become equal to the stars[j], // append star if (j < stars.length && i == stars[j]) { ans += '*'; j++; } ans += s.charAt(i); } return ans; } // Driver Code public static void main(String[] args) { String str = "neveropen"; int chars[] = { 1, 5, 7, 9 }; String ans = addStars(str, chars); // Printing the resultant string System.out.println(ans); }}// This code is contributed by Rohit Pradhan |
Python3
# Python3 code to implement the above approach# Function to add starsdef addStars(s, stars) : # Create a string ans for storing # resultant string ans = ""; j = 0; for i in range(len(s)) : # If the count of characters # become equal to the stars[j], # append star if (j < len(stars) and i == stars[j]) : ans += '*'; j += 1; ans += s[i]; return ans;# Driver codeif __name__ == "__main__" : string = "neveropen"; chars = [ 1, 5, 7, 9 ]; ans = addStars(string, chars); # Printing the resultant string print(ans); # This code is contributed by AnkThon |
C#
// C# code to implement the approachusing System;using System.Collections;public class GFG { // Function to add stars public static string addStars(string s, int[] stars) { // Create a string ans for storing // resultant string string ans = ""; int j = 0; for (int i = 0; i < s.Length; i++) { // If the count of characters // become equal to the stars[j], // append star if (j < stars.Length && i == stars[j]) { ans += '*'; j++; } ans += s[i]; } return ans; } // Driver code public static void Main(string[] args) { string str = "neveropen"; int[] chars = { 1, 5, 7, 9 }; string ans = addStars(str, chars); // Printing the resultant string Console.Write(ans); }}// This code is contributed by garg28harsh. |
Javascript
// Javascript code to implement the approach// Function to add starsfunction addStars(s, stars) { // Create a string ans for storing // resultant string let ans = ""; let j = 0; for (let i = 0; i < s.length; i++) { // If the count of characters // become equal to the stars[j], // append star if (j < stars.length && i == stars[j]) { ans += '*'; j++; } ans += s[i]; } return ans;}// Driver codelet str = "neveropen";let chars = [1, 5, 7, 9];let ans = addStars(str, chars);// Printing the resultant stringconsole.log(ans)// This code is contributed by Saurabh Jaiswal |
g*eeks*fo*rg*eeks
Time Complexity: O(N)
Auxiliary Space: O(N)
Approach: using inbuilt insert function.
In this approach we need to increase the length of orignal string as on insert operation the orignal string get modified and so the target index needs to be increased by 1 so we used k.
The addStars function inserts an asterisk (*) at the positions specified in the chars vector. Here’s step by step approach for same:
- The addStars function takes a string s and a vector of integers stars as input.
- It iterates through the stars vector using a for loop.
- For each position specified in the stars vector, it inserts an asterisk (*) at that position in the string s(using insert function).
- we increment the k on insertion because size increases on an insertion operation.
- The updated string is returned.
C++
#include <iostream>#include <vector>#include <string>using namespace std;// Function to add starsstring addStars(string s, vector<int>& stars){ // Iterate through the vector of positions int k=0; for (int i = 0; i < stars.size(); i++) { // Insert a star at the specified position s.insert(stars[i]+ k++, "*"); } return s;}// Driver codeint main(){ string str = "neveropen"; vector<int> chars = { 1, 5, 7, 9 }; string ans = addStars(str, chars); // Printing the resultant string cout << ans << endl;} |
Java
import java.util.ArrayList;import java.util.List;public class GFG { // Function to add stars public static String addStars(String s, List<Integer> stars) { // Iterate through the vector of positions int k = 0; for (int i = 0; i < stars.size(); i++) { // Insert a star at the specified position s = s.substring(0, stars.get(i) + k) + "*" + s.substring(stars.get(i) + k); k++; } // Return result return s; } public static void main(String[] args) { // Test case String str = "neveropen"; List<Integer> chars = new ArrayList<>(); chars.add(1); chars.add(5); chars.add(7); chars.add(9); String ans = addStars(str, chars); System.out.println(ans); }} |
Python3
# Function to add starsdef addStars(s, stars): # Iterate through the vector of positions k = 0 for i in range(len(stars)): # Insert a star at the specified position s = s[:stars[i]+k] + "*" + s[stars[i]+k:] k += 1 return s# Driver codestr = "neveropen"chars = [1, 5, 7, 9]ans = addStars(str, chars)# Printing the resultant stringprint(ans) |
C#
using System;using System.Collections.Generic;namespace CodeTranslation{ class Program { // Function to add stars static string AddStars(string s, List<int> stars) { // Iterate through the list of positions int k = 0; for (int i = 0; i < stars.Count; i++) { // Insert a star at the specified position s = s.Insert(stars[i] + k++, "*"); } return s; } // Driver code static void Main(string[] args) { string str = "neveropen"; List<int> chars = new List<int> { 1, 5, 7, 9 }; string ans = AddStars(str, chars); // Printing the resultant string Console.WriteLine(ans); } }} |
Javascript
// Function to add starsfunction addStars(s, stars) { // Iterate through the vector of positions let k = 0; for (let i = 0; i < stars.length; i++) { // Insert a star at the specified position s = s.slice(0, stars[i] + k) + "*" + s.slice(stars[i] + k); k += 1; } // Return result return s;}// Test caselet str = "neveropen";let chars = [1, 5, 7, 9];let ans = addStars(str, chars);console.log(ans); |
g*eeks*fo*rg*eeks
Time Complexity: O(N*K)
Auxiliary Space: O(N)
Explaination:
The time complexity of this approach is O(n*k), where n is the length of the string and k is the size of the vector. This is because for each position in the vector, we need to insert an asterisk into the string, which takes O(n) time.
The auxiliary space complexity is O(1), as we are not using any additional data structures.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
