Walmart Labs Interview Question
Software DevelopersCountry: India
Interview Type: Written Test
#include<bits/stdc++.h>
using namespace std;
int main(){
string s1,s2;
cin>>s1>>s2;
int l1=s1.length(),l2=s2.length();
int ans=INT_MAX;
if(l2>l1){
cout<<-1<<endl; // not possible
return 0;
}
for(int i=0 ; i<l1-l2+1 ; i++){
string temp=s1.substr(0,i)+s2+s1.substr(i+l2); // place s2 in all possible positions in s1
int cost=0;
// calculate cost to place s2
for(int j=i ; j<i+l2 ; j++){
if(s1[j]!=temp[j])
cost++;
}
int z=0;
// find the cost to convert new string to palindrome
for(int j=0 ; j<ceil(l1/2.0) ; j++){
if((j<i || j>=i+l2) && temp[j]!=temp[l1-j-1]) // if s2 is in the first half of new string
cost++;
else if(temp[j]!=temp[l1-j-1] && (l1-j-1<i || l1-j-1>=i+l2)) // if s2 is in the second half of new string
cost++;
else if(temp[j]!=temp[l1-j-1]){ // if s2 is in both halves
z=1;
break;
}
}
if(z==0)
ans=min(ans,cost);
}
if(ans==INT_MAX)
cout<<-1<<endl;
else
cout<<ans<<endl;
return 0;
}
Python Code
def count_op(s1,s2):
if s1==s2:
return 0
replace = 0
d1={};d2={}
for i in s1:
d1[i] = d1.get(i,0)+1
for i in s2:
d2[i] = d2.get(i,0)+1
for i in d2:
if i not in d1:
replace+= d2[i]
elif d2[i]>d1[i]:
replace+= d2[i] - d1[i]
return replace
s1 = input()
s2= input()
print(count_op(s1,s2))
import java.io.*;
import java.util.*;
import java.lang.*;
public class substringpalindrome
{
public static void main(String args[])
{
String s1,s2,snew,sleft,sright,rev;
int l1,l2;
Scanner s=new Scanner(System.in);
int[] arr=new int[20];
s1=s.next();
s2=s.next();
l1=s1.length();
l2=s2.length();
int count=0,mini=9999;
for(int i=0;i<=l1-l2;i++)
{
if(i==0)
{
sleft=s2;
sright=s1.substring(i+l2,l1);
snew=sleft+sright;
}
else
{
sleft=s1.substring(0,i);
sright=s2;
snew=sleft+sright+s1.substring(i+l2,l1);
}
StringBuilder sb=new StringBuilder(snew);
sb.reverse();
rev=sb.toString();
if(snew.equals(rev))
{
for(int j=0;j<s2.length();j++)
{
if(s2.charAt(j)!=s1.charAt(i+j))
{
count+=1;
}
}
if(count<mini)
{
mini=count;
}
}
}
System.out.println(mini);
}
}
import java.io.*;
import java.util.*;
import java.lang.*;
public class substringplaindrome
{
public static void main(String args[])
{
String s1,s2,snew,sleft,sright,rev;
int l1,l2;
Scanner s=new Scanner(System.in);
int[] arr=new int[20];
s1=s.next();
s2=s.next();
l1=s1.length();
l2=s2.length();
int count=0,mini=9999;
for(int i=0;i<=l1-l2;i++)
{
if(i==0)
{
sleft=s2;
sright=s1.substring(i+l2,l1);
snew=sleft+sright;
}
else
{
sleft=s1.substring(0,i);
sright=s2;
snew=sleft+sright+s1.substring(i+l2,l1);
}
StringBuilder sb=new StringBuilder(snew);
sb.reverse();
rev=sb.toString();
if(snew.equals(rev))
{
for(int j=0;j<s2.length();j++)
{
if(s2.charAt(j)!=s1.charAt(i+j))
{
count+=1;
}
}
if(count<mini)
{
mini=count;
}
}
}
System.out.println(mini);
}
}
simple java solution
import java.io.*;
import java.util.*;
import java.lang.*;
public class substringpalindrome
{
public static void main(String args[])
{
String s1,s2,snew,sleft,sright,rev;
int l1,l2;
Scanner s=new Scanner(System.in);
int[] arr=new int[20];
s1=s.next();
s2=s.next();
l1=s1.length();
l2=s2.length();
int count=0,mini=9999;
for(int i=0;i<=l1-l2;i++)
{
if(i==0)
{
sleft=s2;
sright=s1.substring(i+l2,l1);
snew=sleft+sright;
}
else
{
sleft=s1.substring(0,i);
sright=s2;
snew=sleft+sright+s1.substring(i+l2,l1);
}
StringBuilder sb=new StringBuilder(snew);
sb.reverse();
rev=sb.toString();
if(snew.equals(rev))
{
for(int j=0;j<s2.length();j++)
{
if(s2.charAt(j)!=s1.charAt(i+j))
{
count+=1;
}
}
if(count<mini)
{
mini=count;
}
}
}
System.out.println(mini);
}
}
What about the case s1 = "abc" and s2 = "def"?
- Raghu October 18, 2018