LAPIN - Editorial

editorial
, , , ,
1

Problem Link:

Practice

Contest

Video Editorial

Difficulty:

Cakewalk

Pre-requisites:

ad-hoc

Problem:

Given a string S, if we split it in the middle (if S has an odd number of characters, disregard the middle character), then if the frequency of each character is the same in both halves, S is called a “lapindrome”. Given the string S, test if it is a Lapindrome or not.

Explanation:

Maintain frequencies for the left half and the right half, for each character. After computing the frequency of each half, then check if the frequencies of all characters match. If so, output “YES”, else output “NO”.

Consider the following pseudocode:


bool isLapin(S)
	initialize cntL[] and cntR[] with 0
	L = S.length()
	for(i = 0; i < L/2; i++)
		cntL[S[i]-'a']++
	for(i = (L+1)/2; i < L; i++)
		cntR[S[i]-'a']++
	bool ret = true
	for(c = 0; c < 26; c++)
		if(cntL[c] != cntR[c])
			ret = false
	return ret

The time complexity for this is O(|S| + 26) per test-case.

Setter’s Solution:

Can be found here

Tester’s Solution:

Can be found here

Video Editorial

10 Likes
2

Links broken?

4 Likes
3

I used a different approach, I divided the string into two equal substrings by splitting it from the middle and then sorted both the substrings, since for true case (“YES”) the frequency of the characters in both the original substrings is same, so after sorting the substrings we should get identical substrings. So after sorting we just check if the sorted substrings are same of not. Here’s my solution :- CodeChef: Practical coding for everyone

15 Likes
4

can somebody trace bugs in my solution pls.
:- CodeChef: Practical coding for everyone

the program satisfies all test cases…

5

http://www.codechef.com/viewsolution/3258850

please tell the problem with my solution…
the given testcases for the question are giving the correct output…
and i have also tried some more test cases of my own…
but i am getting a wrong answer

6

Getting WA.Help please

http://www.codechef.com/viewsolution/5213313

7

@biprotip: Hey try to increase the size of the array. It is always better to increase the array size than the required. here 1 will be needed for the ‘\0’. And try with instead of using 2 variables use 2 array of size 26 and increase each index with left[ch[i]-‘a’]++ and same with the right array. Finally check if both the arrays are equal. If you have any doubt just look at this solution

1 Like
8
9

whats wrong with this code?

10

can someone please tell why is it giving wa?

CodeChef: Practical coding for everyonelink text

11

#include
#include
#include<string.h>
#include
using namespace std;
main(){
int t;
cin>>t;
for(int i=0;i<t;i++){
string s;
cin>>s;
int p=s.size()/2;
char A[p],B[p];
for(int j=0;j<p;j++){A[j]=s[j];}
for(int j=s.size()-1,k=0;j>=p;j–,k++){B[k]=s[j];}
sort(A,A+p);
sort(B,B+p);
vector v1§;
vector v2§;
vector ::iterator it1;
vector ::iterator it2;
it1=unique_copy(A,A+p,v1.begin());
it2=unique_copy(B,B+p,v2.begin());
v1.resize(it1-v1.begin());
v2.resize(it2-v2.begin());
//int p1=v1.size();
//sort(v1,v1+p1)
if(v1.size()!=v2.size()){cout<<“NO”<<endl;}
else{
int k1=0;
for(int j=0;j<v1.size();j++){
if(v1[j]!=v2[j]){k1++;}
}
int a[v1.size()],b[v2.size()];
for(int j=0;j<v1.size();j++){
int k2=0;
for(int k=0;k<p;k++){
if(v1[j]==A[k]){k2++;}
}
a[j]=k2;
}

for(int j=0;j<v2.size();j++){
int k2=0;
for(int k=0;k<p;k++){
if(v2[j]==B[k]){k2++;}
}
b[j]=k2;
}

int k3=0;
for(int j=0;j<v1.size();j++){
if(a[j]!=b[j]){k3++;}
}

if(k3>0 || k1>0){cout<<“NO”<<endl;}
else{cout<<“YES”<<endl;}

}

}
}

12

@jaggu8

Its a bit difficult to have a good look over your code atm. I strongly advise that you either givea submission link to your code, or edit the post (select your code, and THEN press button “insert code”)

But by what I could get, I will say just make 2 arrays - int a[26], b[26] and increase the frequency of letters you encounter in the half of string.

Eg-
for (i= 0; i <n /2; i++)
{
arr[s[i]-‘a’]++;
}

EDIT: Something seems wrong with this insert code thing atm. I just cant make it write my code properly like I used to…

13

i am unable to find out error please help me



#include<stdio.h>

#include<string.h>

int main()

{

int t,c,start,end,flag,i;

char s[1000];

scanf("%d",&t);

while(t–)

{

flag=0;

scanf("%s",s);

c=strlen(s);

if(c%2==0)

start=c/2;

else

start=c/2+1;

end=c/2-1;

		for(i=0;i<=end;i++)
		{
			if(s[i]==s[start++])
			continue;
			else{
				flag=1;
				break;
			}
		}
	
if(flag==0)
printf("YES\n");
else 	printf("NO\n");
}
return 0;



}
14

plz help me out…!

Link

15

Hey there, Can somebody solve my problem regarding LAPIN.
According to the question, zyzxyz is not lapindrome but my code, which has been accepted by the compiler gives YES to it.
I am confused…

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