You are not logged in. Please login at www.codechef.com to post your questions!

×

LAPIN - Editorial

6
1

Problem Link:

Practice
Contest

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

This question is marked "community wiki".

asked 18 Jun '13, 16:17

pragrame's gravatar image

6★pragrame ♦♦
963568379
accept rate: 14%

edited 19 Jun '13, 14:13

admin's gravatar image

0★admin ♦♦
17.4k347486515


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 :- http://www.codechef.com/viewsolution/2196881

link

answered 18 Jun '13, 18:32

v_akshay's gravatar image

4★v_akshay
1.2k91625
accept rate: 13%

edited 18 Jun '13, 18:35

4

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

(18 Jun '13, 19:02) spandanpathak2★

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

(18 Jun '13, 19:25) sumanth2324★
3

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" :P

(18 Jun '13, 20:03) pragrame ♦♦6★

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

(18 Jun '13, 20:32) v_akshay4★

Links broken?

link

answered 18 Jun '13, 17:32

vivekiitkgp's gravatar image

2★vivekiitkgp
13116
accept rate: 14%

can somebody trace bugs in my solution pls. :- http://www.codechef.com/viewsolution/2205187

the program satisfies all test cases..

link

answered 18 Jun '13, 22:45

aayushnul's gravatar image

2★aayushnul
161
accept rate: 0%

edited 18 Jun '13, 22:46

3

Here is your AC code with array size increased. http://www.codechef.com/viewsolution/2279176

(18 Jun '13, 22:48) bugkiller3★

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

link

answered 15 Jan '14, 23:51

insaynasasin's gravatar image

1★insaynasasin
1054811
accept rate: 0%

try this: 1 abac

(16 Jan '14, 00:23) vytenis6★

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

(16 Jan '14, 00:31) garakchy1★

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

(16 Jan '14, 00:36) insaynasasin1★

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

(16 Jan '14, 00:38) insaynasasin1★

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

(16 Jan '14, 00:40) insaynasasin1★

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

(16 Jan '14, 00:55) garakchy1★

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

(16 Jan '14, 00:56) garakchy1★
showing 5 of 7 show all
link

answered 25 Oct '14, 02:33

biprotip's gravatar image

3★biprotip
7114
accept rate: 0%

@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

link

answered 25 Oct '14, 20:45

bipin2's gravatar image

3★bipin2
3.1k254670
accept rate: 8%

link

answered 14 Mar '16, 18:36

amrit008's gravatar image

2★amrit008
11
accept rate: 0%

whats wrong with this code?

link

answered 14 Mar '16, 18:36

amrit008's gravatar image

2★amrit008
11
accept rate: 0%

can someone please tell why is it giving wa?

https://www.codechef.com/viewsolution/10264664link text

link

answered 02 Jun '16, 03:42

dove89's gravatar image

0★dove89
1
accept rate: 0%

include<iostream>

include<algorithm>

include<string.h>

include<vector>

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<char> v1(p); vector<char> v2(p); vector<char> ::iterator it1; vector<char> ::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;}

}

} }

link

answered 28 Jan, 11:38

jaggu8's gravatar image

2★jaggu8
1
accept rate: 0%

why is this wrong

(28 Jan, 11:39) jaggu82★

@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....

link

answered 28 Jan, 13:18

vijju123's gravatar image

4★vijju123 ♦
11.3k1316
accept rate: 18%

edited 28 Jan, 13:21

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;

}

link

answered 09 Feb, 09:37

abinashhota's gravatar image

3★abinashhota
1
accept rate: 0%

plz help me out...!

Link

link

answered 06 Apr, 00:43

palash7563's gravatar image

2★palash7563
153
accept rate: 0%

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....

link

answered 10 Jun, 09:14

rupali_patel's gravatar image

2★rupali_patel
11
accept rate: 0%

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

link

answered 25 Oct, 13:15

gangadhar7's gravatar image

0★gangadhar7
1
accept rate: 0%

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

link

answered 18 Nov, 17:00

batman69's gravatar image

2★batman69
0
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,235
×1,147
×787
×27
×7

question asked: 18 Jun '13, 16:17

question was seen: 5,218 times

last updated: 18 Nov, 17:00