Linkedin placement test question: Get Palindrome of a String with replacement

Elina has a string S, consisting of lowercase English alphabetic letters(ie. a-z). She can replace any character in the string with any other character, and she can perform this replacement any number of times. she wants to create a palindromic string, p , from s such that string p contains the sub string linkedin . it is guaranteed that Elina can create palindromic string p from S. find the minimum number of operation required to create palindromic string p from S. Sample test case are:

First test case: S=“linkedininininin”

explanation :

        linkedin (i) (n) (i) (n) (i) ni (n)

                 (n) (i) (d) (e) (k)    (l)  

        p =  "linkedinnideknil" 

output is 6

Second test case: S=“fulrokxeuolnzxltiiniabudyyozvulqbydmaldbxaddmkobhlplkaplgndnksqidkaenxdacqtsskdkdddls”

output is 46

Hi , where did you write the test? can you please give that detail ?

Fix each substring of length 8 , convert that part of substring into linkedin and count the operation , and then after it , convert the change string into pallendromic string and count the operation. Do this for each possible substring of length 8 , and take the minimum of all.

1 Like

For answering the question let’s first see what a recursive palindromic function would look like-

func pal(s){
If len(s) <= 1: True
Else if the first and last element are the same then you check -  pal of s[2]("second element") to s[-2]("second last elemnt")
Else False
}

This shows us that first we need to check the first and last element and then the second and the second last element element and so on… and if they are not same we can do ans += 1

So…

s = input()
ans = 0
for index = 0 to floor(length(s)/2) i ++ {
if s[index] != s[length(s)-index]: ans ++
} 

Hopefully that helps.

There is a similar problem in Codechef. Refer the links below -

Problem - LUCKYPAL

Editorial- LUCKYPAL

3 Likes

@vipsharmavip, your approach is correct but not completely, the correct algo. should be -

  1. find the center of the string.
  2. one by one convert all the 8 length sub-string before center into “linkedin” and calculate answer each time and .
  3. do the same thing as in step-2 but this time take all 8 length sub-strings from the center to the end and calculate the answer.
  4. take the minimum of all the answer that will give the optimum answer.

@vipsharmavip consider the following case:
string is “aaaalinkedinaaaa” from your algo changing substring[4-11] to “linkedin” will take 0 cost and then converting it to palindrome will take 4 cost, so answer will be “4”, but it is not correct ,because after this when you will convert it to palindrome the final string will be “aaaalinkknilaaaa” which does not contain linked as a substring , so the first condition is violated , so I think above suggested changes are required.

5 Likes

for these 2 test cases answer is right. code snippet of the solution:
#include<bits/stdc++.h>

using namespace std;
#define MAX 1000
#define PTRLEN 100

int diff(char* user,char* ptr)
{
int count=0;
for(int i=0;i<strlen(ptr);i++){
if(user[i]!=ptr[i])
count++;
}
return count;
}

void change_diff(char* user,char* ptr, int pos)
{
for(int i=pos,j=0;i<(pos+strlen(ptr));i++,j++){
user[i]=ptr[j];
}
}

int change_palin(char* user,int pos)
{
int count=0;
for(int i=strlen(user)/2;i<strlen(user);i++){
if(user[strlen(user)-i-1]!=user[i]){
count++;
if(pos>=strlen(user)/2)
user[strlen(user)-i-1]=user[i];
else
user[i]=user[strlen(user)-i-1];
}
}
return count;
}

int main()
{
int Num_Test;
ifstream fin;
freopen(“linked.in”,“r”,stdin);
cin>>Num_Test;
for(int iter=0;iter<Num_Test;iter++){
char* user=new char[MAX];
char* ptr=new char[PTRLEN];
memset(user,’\0’,MAX);
memset(ptr,’\0’,PTRLEN);
// fin>>user>>ptr;

cin>>user;
cout<<"USER INPUT STRING:"<<user<<endl;
cin>>ptr;
cout<<"DYNAMIC STRING:"<<ptr<<endl;
if(strlen(user)<2*strlen(ptr))
	cout<<"	STRING IS: "<<user<<endl<<"	MIN CHANGE: "<<"INVALID CASE"<<endl;

else{
	int min=9999,pos=0;
	for(int i=0;i<=(strlen(user)-strlen(ptr));i++){
		char* temp=user;
		if(i<(strlen(user)/2) && (i+strlen(ptr)>(strlen(user)/2)))
			continue;
		if(!strncmp(&temp[i],ptr,strlen(ptr))){
			min=0;
			pos=i;
			break;
		}	
		int max_diff=diff(&temp[i],ptr);
		if(min>max_diff){
			pos=i;
			min=max_diff;
		}
	}
	change_diff(user,ptr,pos);
	min+=change_palin(user,pos);
	cout<<"CASE #"<<iter+1<<":\n";
	cout<<"	STRING IS: "<<user<<endl<<"	MIN CHANGE: "<<min<<endl;
}
}
return 0;

}

@chari407 search for linkedin placement test hackerrank in google.
open the first link.

@vipsharmavip , can you provide the code for “convert the change string into pallendromic string and count the operation”.

I am getting 44 for second test case instead of 46

int Count(string x){
int ans = 0;
for(int i = 0 ; i < x.size()/2 ; ++i )
if(x[i] != x[x.size() - 1 - i])
++ans;
return ans;
}

Oh sorry, I forget to mention that case,

1 Like

@kay_kay, Thanks man

1 Like