LAPIN - Editorial

editorial
, , , ,
16

import java.util.HashMap;
import java.util.Scanner;

class LAPIN {
public static void main(String[] args) throws Exception {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
for (int i = 0; i < t; i++) {
String s = scanner.next();
int half = s.length() / 2;
String s1 = s.substring(0, half);
String s2 = s.substring(half, s.length());
HashMap<Character, Integer> map1 = new HashMap<Character, Integer>();
for (int j = 0; j < s1.length(); j++) {
if (!map1.containsKey(s1.charAt(j))) {
map1.put(s1.charAt(j), 1);
} else {
map1.put(s1.charAt(j), map1.get(s1.charAt(j) + 1));
}
}
HashMap<Character, Integer> map2 = new HashMap<Character, Integer>();
int k = s2.length() % 2 != 0 ? 1 : 0;
for (; k < s2.length(); k++) {
if (!map2.containsKey(s2.charAt(k))) {
map2.put(s2.charAt(k), 1);
} else {
map2.put(s2.charAt(k), map2.get(s2.charAt(k) + 1));
}
}
if (map1.equals(map2)) {
System.out.println(“YES”);
} else {
System.out.println(“NO”);
}

	}

}

}

It passed all the test cases in my local but when I submit my code it showing the wrong answer. Can somebody help me, please

17

i got WA becoz i was priniting “Yes” instead of “YES” .
lol

2 Likes
18

Hello, pls anyone give me the test cases for which the following code doesn’t work : CodeChef: Practical coding for everyone ??

(LAPIN)

19

Plz help me to solve this problem with given my code.

Click here to see my code.

Thank you!!!

20

This satisfies all test cases but I get wrong answer.

Link to solution:
https://www.codechef.com/viewsolution/17144359

21

Help Me please !!

I am unable to find and rectify the error in the following :

#include <bits/stdc++.h>
#include <string>

using namespace std;

#define N 1000000007
#define ll long long



int main()
{
ll t;
cin>>t;
while(t--)
{

    string s;
    cin>>s;
    ll l;
    if(s.length()%2==0)
      {
        l=s.length()/2;
      }
else{
    l=(s.length()-1)/2;
}
char a1[l],a2[l];

if(s.length()%2==0)
{
    for(int i=0;i<l;i++)
{
    a1[i]=s[i];
    a2[i]=s[i+l];
}
}
else{
    for(int i=0;i<l;i++)
{
    a1[i]=s[i];
    a2[i]=s[i+l+1];
}
}

a1[l]='\0';
a2[l]='\0';
sort(a1,a1+l);
sort(a2,a2+l);
bool isSame=true;
for(int i=0;i<l;i++)
{
    if(a1[i]!=a2[i])
    {
        isSame=false;
        break;
    }
}
if(isSame)
{
    cout<<"YES\n";
}
else{
    cout<<"NO\n";
}

}

return 0;

}

It is satisfying all test cases but getting a WA.

22

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

Would appreicate some help here! Using similar logic. Works with multiple test cases on other online compilers. Char array is 1 more than 1000 for ‘\0’. specially added condition when s<1. getting WA with or without the s condition. Please help!

CodeChef: Practical coding for everyone here’s the link in python. Still wont work. The one with editorial logic worked but this doesnt even with multiple testcases on the codechef compiler. Pleas help!!!

23

want a cookie :P…why complicate a cake-walk !

4 Likes
24

@v_akshay , that will increase the complexity from O(n) to O(nlogn)

25

Oh @v_akshay, nice!

So, basically I could rewrite isLapin as follows:


isLapin(string S)
{
    int len = S.length();
    int r1 = len/2, l2 = (len+1)/2;
    sort(S.begin(), S.begin() + r1);
    sort(S.begin() + l2, S.end());
    return S.substr(0, r1) == S.substr(l2);
}

@spandanpathak, surely this can’t be called “complicating” :stuck_out_tongue:

3 Likes
26

@sumanth232 , well, I know that but we have |S|<=1000, so O(nlogn) is well under time constraints :slight_smile: .
@pragrame , thanks :slight_smile: , and perfect implementation :slight_smile:

27

Here is your AC code with array size increased. CodeChef: Practical coding for everyone

3 Likes
28

try this:
1
abac

29

@insaynasasin imho, you tried to convert chars in your string array to ints. try left[arr[i]-‘a’], right[arr[i]-‘a’]

30

@garakchy but what is the difference between the two formats?

31

@garakchy no luck, it is still giving the right answers for the given testcases but on submission, its a wa

32

@vytenis
my code is saying yes for the given string
and that is worng
i get the point

33

was trying since yesterday, lol, and i just got ac on the problem.

34

and i used memcmp, that is a bit faster than every array index comparison imho, try that also @insaynasasin

35

why is this wrong