# Problem Link:

# 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*-‘a’]++

for(i = (L+1)/2; i < L; i++)

cntR[S*-‘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