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.
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:
initialize cntL and cntR with 0
L = S.length()
for(i = 0; i < L/2; i++)
for(i = (L+1)/2; i < L; i++)
bool ret = true
for(c = 0; c < 26; c++)
if(cntL[c] != cntR[c])
ret = false
The time complexity for this is O(|S| + 26) per test-case.
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
@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