# LAPIN - Editorial

Okay thank you for helping me !!

1 Like

thanks once again ssjgz can u tell me how to generate testcases

Hereâ€™s lapindrome complete with testcase generator:

``````// Simon St James (ssjgz) - 2019-10-29
//
// Solution to: https://www.codechef.com/problems/LAPIN
//
#include <iostream>
#include <array>

#include <cassert>

#include <sys/time.h> // TODO - this is only for random testcase generation.  Remove it when you don't need new random testcases!

using namespace std;

template <typename T>
{
assert(cin);
}

constexpr auto numLetters = 26;

array<int, numLetters> letterHistogram(const string& s)
{
array<int, numLetters> letterHistogram = {};
for (const auto letter : s)
{
letterHistogram[letter - 'a']++;
}
return letterHistogram;
}

bool isLapindrome(const string& s)
{
const int length = s.length();
const auto leftHalf = s.substr(0, length / 2);
const auto rightHalf = s.substr(length - length / 2);

return letterHistogram(leftHalf) == letterHistogram(rightHalf);
}

#if 0
SolutionType solveOptimised()
{
SolutionType result;

return result;
}
#endif

int main(int argc, char* argv[])
{
ios::sync_with_stdio(false);
if (argc == 2 && string(argv[1]) == "--test")
{
struct timeval time;
gettimeofday(&time,NULL);
srand((time.tv_sec * 1000) + (time.tv_usec / 1000));
//const int T = rand() % 100 + 1;
const int T = 1;
cout << T << endl;

for (int t = 0; t < T; t++)
{
const int len = 1 + rand() % 12;
const int maxChar = 1 + rand() % numLetters;

string s;
for (int i = 0; i < len; i++)
{
s.push_back('a' + rand() % maxChar);
}
cout << s << endl;
}

return 0;
}

for (int t = 0; t < T; t++)
{

cout << (isLapindrome(s) ? "YES" : "NO") << endl;
}

assert(cin);
}
``````

To generate a testcase, just run the executable and pass it the `--test` flag on the command-line e.g if the executable is called `a.out`:

``````./a.out --test
``````

1 Like

The implementation of the logic as given in Editorial in Python3

``````t = int(input())
while(t>0):
d =  {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
s = input()
ln = len(s)
fg = 0
s1 = ""
s2 = ""
if(ln % 2 == 0):
s1 = s[:ln//2]
s2 = s[ln//2:]
# print(s1, s2)
else:
s1 = s[:ln//2]
s2 = s[(ln//2)+1:]
# print(s1, s2)

for i in s1:
d[i] += 1

for j in s2:
d[j] -= 1

# print(d)

for i in d.values():
if(i != 0):
fg = 1
break
if(fg == 1):
print("NO")
else:
print("YES")
t -= 1``````

Can somebody help me out whats wrong in my code?
https://www.codechef.com/viewsolution/30273757

Consider the testcase:

``````5
bbcccbe
gedce
eccbdde
bdfbdbe
egafded
``````
3 Likes

tnx broâ€¦i got itâ€¦i didnâ€™t clear the map.

1 Like

Even better would be to just write your code so that this kind of problem simply canâ€™t happen in the first place; none of `l`,`l1`,`i`,`s` or `m` are used outside of the `while` block, so why declare them there?

``````#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t--)
{
int l,l1,i;
string s;
map<char,int> m;
cin>>s;
l=s.size()/2;
if(l==0)
{
cout<<"NO\n";
continue;
}
if(s.size()%2==0)
{

l1=l;
}
else
{
l1=l+1;
}
i=l1;
while(i<s.size())
{
if(m.find(s[i])==m.end())
{
m.insert(pair<char,int>(s[i],1));
}
else
m[s[i]]++;
i++;
}
for(i=0;i<l;i++)
{
if(m.find(s[i])==m.end()|| m[s[i]]==0)
{
cout<<"NO\n";
break;
}
else
m[s[i]]--;
}
if(i==l)
{
cout<<"YES\n";
}
}
return 0;
}
``````

or better still:

``````#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
const int l=s.size()/2;
if(l==0)
{
cout<<"NO\n";
continue;
}
int l1 = l;
if(s.size()%2!=0)
{
l1=l + 1;
}
int i=l1;
map<char,int> m;
while(i<s.size())
{
if(m.find(s[i])==m.end())
{
m.insert(pair<char,int>(s[i],1));
}
else
m[s[i]]++;
i++;
}
for(i=0;i<l;i++)
{
if(m.find(s[i])==m.end()|| m[s[i]]==0)
{
cout<<"NO\n";
break;
}
else
m[s[i]]--;
}
if(i==l)
{
cout<<"YES\n";
}
}
return 0;
}
``````
4 Likes

but there may be repeated memory allocation and memory release for themâ€¦ will it affect performance of code?

The construction of an empty `string` or an empty `map` should not involve memory allocations.

1 Like

got it â€¦Thank you sirâ€¦

1 Like

whats wrong in this solution

# include<bits/stdc++.h>

using namespace std;

int main()
{
int i,j,count=0;
int t;
cin>>t;
while(tâ€“)
{ int n;
string s;
cin>>s;
n=s.length();
if(n%2==0)
{
for(i=0;i<n/2;i++)
{
for(j=n/2;j<n;j++)
{
if(s[i]==s[j])
{
count++;
}
}

``````						}
if(count==n/2)
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
else if(n%2!=0)
{
for(i=0;i<n/2;i++)
{
for(j=(n+1)/2;j<n;j++)
{
if(s[i]==s[j])
{
count++;
}
}

}
if(count==n/2)
cout<<"yes"<<endl;
else
cout<<"no"<<endl;

}
}
return 0;
}``````

My approach using Counter in python,
Have a look :
https://www.codechef.com/viewsolution/33027780

There must be some issue with the test cases.
I think there is a non-lowercase english alphabet somewhere (the question specifies only lowercase english alphabets are in the input)

I donâ€™t see any other reason why my solution wouldnâ€™t work : https://www.codechef.com/viewsolution/34547143

If someone finds an issue. Please let me know, thanks

https://www.codechef.com/viewsolution/35751966

May I know why the output donâ€™t match

Repllies will be appreciated #CodeChef-DSA-learners #editorial #help #lapindrome

https://www.codechef.com/viewsolution/36790347

I Couldâ€™t understand that whatâ€™s the error in this code.
If I Put Mannual Input in this code. Its Execute sucessfully and shows the correct output. but when i submitted , this is showing wrong answer.
What should i do?

I have tried different approach . I divide the string into two and add ASCII of both strings. C1 for left ASCII and C2 for right ASCII. if both are same then they are lapindrome. My code passes the test cases But still i am getting wrong answer. Somebody help.

#include
using namespace std;
int islapin(string s){
int len=s.length();
int c1=0,c2=0,l;
bool r=true;
if(len%2 !=0){
r=false;
}
l=len/2;
for(int i=0;i<len;i++){
if(i<l){
c1+=(int)s[i];
}else if(i==l && r==false){
continue;
}else{
c2+=(int)s[i];
}
}

``````if(c1!=c2){
return 1;
}else{
return 0;
}
``````

}
int main(){
int n;
cin>>n;
int a=(int)calloc(n,sizeof(int));
string s;

``````for(int i=0;i<n;i++){
cin>>s;
if(islapin(s)){
a[i]=1;
}
}

for(int i=0;i<n;i++){
if(a[i]==1){
cout<<"NO"<<endl;
}else{
cout<<"YES"<<endl;
}
}
return 0;
``````

}