Improve Article
Save Article
Given a string s and an array spaces[] describing the original string’s indices where spaces will be added. The task is to add spaces in given positions in spaces[] and print the string formed.
Examples:
Input: s = “GeeksForGeeK”, spaces = {1, 5, 10}
Output: “G eeks ForGe eK”
Explanation: The underlined characters in “GeeksForGeeK” relate to the indices 1, 5, and 10. After that, put spaces in front of those characters.Input: s = “ilovegeeksforgeek”, spaces = {1, 5, 10, 13}
Output: “i love geeks for geek”
Approach#1: This problem is simple string implementation based. Follow the steps below to solve the given problem.
- Initialize with a space in the new string of size of the sum of the length of both arrays.
- Visit the index and wherever the index is equal to the current space value in the space[] array skip it as space is already there.
- Else keep assigning the value from the main string
- Here addition of ‘l’ in line { if(l<N and i==sp[l]+l) } is
very interesting to observe:
- The values in the space array are basically according to the old input string.
- But in the new string, these space values or indices are basically shifting by the number of spaces found before.
- Print the string formed at the end.
Below is the implementation of the above approach
C++
#include <bits/stdc++.h>
using namespace std;
string spaceintegration(string s, vector<int>& sp)
{
int M = s.size(), N = sp.size(), l = 0, r = 0;
string res(M + N, ' ');
for (int i = 0; i < M + N; i++) {
if (l < N and i == sp[l] + l)
l++;
else
res[i] = s[r++];
}
return res;
}
int main()
{
string s = "ilovegeeksforgeeks";
vector<int> space = { 1, 5, 10, 13 };
cout << spaceintegration(s, space) << endl;
return 0;
}
Java
import java.util.*;
class GFG
{
static String spaceintegration(String s, int []sp)
{
int M = s.length(), N = sp.length, l = 0, r = 0;
String res = newstr(M + N, ' ');
for (int i = 0; i < M + N; i++) {
if (l < N && i == sp[l] + l)
l++;
else
res = res.substring(0,i)+s.charAt(r++)+res.substring(i+1);
}
return res;
}
static String newstr(int i, char c) {
String str = "";
for (int j = 0; j < i; j++) {
str+=c;
}
return str;
}
public static void main(String[] args)
{
String s = "ilovegeeksforgeeks";
int[] space = { 1, 5, 10, 13 };
System.out.print(spaceintegration(s, space) +"\n");
}
}
Python3
def spaceintegration(s, sp):
M = len(s)
N = len(sp)
l = 0
r = 0
res = [' '] * (M + N)
for i in range(M + N):
if (l < N and i == sp[l] + l):
l += 1
else:
res[i] = s[r]
r += 1
return ''.join(res)
if __name__ == "__main__":
s = "ilovegeeksforgeeks"
space = [ 1, 5, 10, 13 ]
print(spaceintegration(s, space))
C#
using System;
class GFG
{
static String spaceintegration(String s, int []sp)
{
int M = s.Length, N = sp.Length, l = 0, r = 0;
String res = newstr(M + N, ' ');
for (int i = 0; i < M + N; i++) {
if (l < N && i == sp[l] + l)
l++;
else
res = res.Substring(0,i)+s[r++]+res.Substring(i+1);
}
return res;
}
static String newstr(int i, char c) {
String str = "";
for (int j = 0; j < i; j++) {
str+=c;
}
return str;
}
public static void Main()
{
String s = "ilovegeeksforgeeks";
int[] space = { 1, 5, 10, 13 };
Console.Write(spaceintegration(s, space) +"\n");
}
}
Javascript
<script>
function spaceintegration(s, sp)
{
let M = s.length, N = sp.length, l = 0, r = 0;
let res = new Array(M + N).fill(' ');
for (let i = 0; i < M + N; i++) {
if (l < N && i == sp[l] + l)
l++;
else
res[i] = s[r++];
}
return res.join('');
}
let s = "ilovegeeksforgeeks";
let space = [1, 5, 10, 13];
document.write(spaceintegration(s, space) + '<br>');
</script>
Output
i love geeks for geeksTime Complexity: O(M+N)
Auxiliary Space: O(M+N)
Approach#2: This problem can be solve by method which we use to insert element at specific position in array. Follow the steps below to solve the given problem.
- We have string s and position in vector space.
- Iterate over the element of
the space From last of vector to first and follow the following steps for every element of vector. Let L element of the vector.
- Add one space at the end of s.
- Iterate over string Till the L:
- Move one-one character forward till L.
- At last Add space at L.
- Print string at the end.
Bellow is the implementation of above approach.
C++
#include <bits/stdc++.h>
using namespace std;
string spaceintegration(string s, vector<int>& space)
{
int y = 0;
int len = space.size();
while (len--) {
int k = space[len] + 1;
int l = s.size() - 1;
string tem = " ";
s += tem;
for (int i = l; i >= k - 1; i--) {
s[i + 1] = s[i];
}
s[k - 1] = tem[0];
y += 1;
}
return s;
}
int main()
{
string s = "ilovegeeksforgeeks";
vector<int> space = { 1, 5, 10, 13 };
cout << spaceintegration(s, space) << endl;
return 0;
}
Python
def spaceintegration(se, space):
s = list(se)
for i in range(len(space)-1, -1, -1):
s.insert(space[i], " ")
return "".join(s)
if __name__ == "__main__":
s = "ilovegeeksforgeeks"
space = [1, 5, 10, 13]
print(spaceintegration(s, space))
C#
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
static string spaceintegration(string s, List<int> space)
{
int y = 0;
int len = space.Count;
while (len > 0) {
len -= 1;
int k = space[len] + 1;
int l = s.Length - 1;
string tem = " ";
s += tem;
for (int i = l - 1 ; i >= k - 1 ; i--) {
s = s.Remove(i + 1, 1);
s = s.Insert(i + 1, Char.ToString(s[i]));
}
s = s.Remove(k - 1, 1);
s = s.Insert(k - 1, Char.ToString(tem[0]));
y += 1;
}
return s;
}
public static void Main(string[] args){
string s = "ilovegeeksforgeeks";
List<int> space = new List<int>{ 1, 5, 10, 13 };
Console.WriteLine(spaceintegration(s, space));
}
}
Javascript
function spaceintegration(s, sp)
{
s = s.split('')
for(let i = sp.length-1; i>=0; i--){
s.splice(sp[i], 0, " ");
}
return s.join('');
}
let s = "ilovegeeksforgeeks";
let space = [1, 5, 10, 13];
console.log(spaceintegration(s,space));
Output
i love geeks for geeksTime Complexity: O(M*N)
Here M is the length of the string and N is the size of space vector.
Auxiliary Space: O(1)
As constant extra space is used.