×

Cakewalk

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

973568379
accept rate: 14%

18.3k347492525

 6 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 answered 18 Jun '13, 18:32 4★v_akshay 1.2k●9●16●25 accept rate: 13% 4 want a cookie :P...why complicate a cake-walk ! (18 Jun '13, 19:02) @v_akshay , that will increase the complexity from O(n) to O(nlogn) (18 Jun '13, 19:25) 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) @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★
 1 Links broken? answered 18 Jun '13, 17:32 131●1●6 accept rate: 14%
 0 can somebody trace bugs in my solution pls. :- http://www.codechef.com/viewsolution/2205187 the program satisfies all test cases.. answered 18 Jun '13, 22:45 16●1 accept rate: 0% 3 Here is your AC code with array size increased. http://www.codechef.com/viewsolution/2279176 (18 Jun '13, 22:48)
 0 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 answered 15 Jan '14, 23:51 105●4●8●11 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) @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) @vytenis my code is saying yes for the given string and that is worng i get the point (16 Jan '14, 00:40) 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
 0 Getting WA.Help please http://www.codechef.com/viewsolution/5213313 answered 25 Oct '14, 02:33 3★biprotip 71●1●4 accept rate: 0%
 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 answered 25 Oct '14, 20:45 3★bipin2 3.1k●25●46●70 accept rate: 8%
 0 answered 14 Mar '16, 18:36 1★amrit008 11 accept rate: 0%
 0 whats wrong with this code? answered 14 Mar '16, 18:36 1★amrit008 11 accept rate: 0%
 0 can someone please tell why is it giving wa? answered 02 Jun '16, 03:42 0★dove89 1 accept rate: 0%

# 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;}

}

} }

2★jaggu8
1
accept rate: 0%

why is this wrong

(28 Jan '17, 11:39) 2★
 0 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
 0 i am unable to find out error please help me include include 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;  }  answered 09 Feb '17, 09:37 1 accept rate: 0%
 0 plz help me out...! Link answered 06 Apr '17, 00:43 15●3 accept rate: 0%
 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.... answered 10 Jun '17, 09:14 11 accept rate: 0%
 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 map1 = new HashMap(); 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 map2 = new HashMap(); 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 answered 25 Oct '17, 13:15 1 accept rate: 0%
 0 i got WA becoz i was priniting "Yes" instead of "YES" . lol answered 18 Nov '17, 17:00 2★batman69 0 accept rate: 0%
 0 Hello, pls anyone give me the test cases for which the following code doesn't work : https://www.codechef.com/viewsolution/16573029 ?? (LAPIN) answered 14 Dec '17, 15:08 0★adarshbl 1 accept rate: 0%
 0 Plz help me to solve this problem with given my code. Click here to see my code. Thank you!!! answered 10 Jan, 16:48 2★mr_shah 1 accept rate: 0%
 0 This satisfies all test cases but I get wrong answer. Link to solution: https://www.codechef.com/viewsolution/17144359 answered 24 Jan, 15:51 1★m7d5_3 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×13,419
×1,278
×818
×27
×7

question asked: 18 Jun '13, 16:17

question was seen: 5,902 times

last updated: 24 Jan, 15:51