LAPIN - Editorial

editorial
, , , ,
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

5 Likes
2

Links broken?

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

5 Likes
4

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

4 Likes
5

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

6

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
7

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

8

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

the program satisfies all test cases…

9

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

3 Likes
10

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

11

try this:
1
abac

12

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

13

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

14

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

15

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

16

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

17

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

18

Getting WA.Help please

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

19

@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

20