Pair Case: C++ program to enter '*' between two identical characters in a string

Here, we are going to implement a C++ program that will enter asterisk (*) between two identical characters in a string.
Submitted by Indrajeet Das, on December 14, 2018

Given a string, compute recursively a new string where identical chars that are adjacent in the original string are separated from each other by a "*".

Sample Input 1: "hello"

Sample Output 1: "hel*lo"

Sample Input 2: "xxyy"

Sample Output 2: "x*xy*y"

Sample Input 3: "aaaa"

Sample Output 3: "a*a*a*a"

Explanation:

In this question, we have to add a star between any pair of same letters. This could be easily achieved using recursion. When the start index is equal to (start + 1) index, we will shift all the letters from (start + 1) by 1 on the right side and on (start + 1), we will add a star.

Algorithm:

STEP 1: Declaring a recursive function pairStar with parameters (char arr[], int start)
STEP 2: Base Case: if(arr[start] == '\0') return;
STEP 3: if(start == start +1)
Shift all the letters from start+1 to right side by 1.
STEP 4: Enter '*' at (start +1) in arr.

Example:

    Input = "aaa"
    First Traversal: "aa*a"
    Second Traversal: "a*a*a"

C++ program:

#include <iostream>
using namespace std;

//Function To find length
int length(char arr[]){
	int len = 0;
	for(int i =0;arr[i]!='\0';i++){
		len++;
	}
	return len;
}

//Recursive Function
void pairStar(char arr[],int start){
	//Base Case: Reached End Of String
	if(arr[start]=='\0'){
		return;
	}   
	//Recursive Call 
	pairStar(arr,start+1);
	if(arr[start] == arr[start+1]){
		int l = length(arr);
		//Extending the string
		arr[l+1] = '\0';
		int i;
		//To shift the letters by 1
		for(i = l-1;i>=start +1;i--){
			arr[i+1] = arr [i];
		}
		//Entering * in between
		arr[start+1] = '*';
	}
}

//Main
int main(){
	char input[50];
	cout<<"Enter Input"<<endl;
	cin>> input;

	pairStar(input,0);  //Calling the function

	cout<<"Modified Output"<<endl;
	cout<<input<<endl;

	return 0;
}

Output

Enter Input
hello
Modified Output
hel*lo