Lapindromes

A lapindrome is a string that, when split in the middle, gives two halves having:

• The same characters

• With the same frequency of each character

If the string length is odd, the middle character is ignored.

Examples of lapindromes:

• gaga → ga and ga

• abccab → abc and cab (same multiset of characters)

• rotor → ro and or (ignore middle t)

• xyzxy → xy and xy

Non-examples:

• abbaab → halves abb and aab → same characters but frequencies differ.

• abcde → halves ab and de → different characters.

Your task: Given a string, check if it is a lapindrome.

Problem Statement:

For each test case:

• You are given a string S (only lowercase English letters).

• Determine whether S is a lapindrome.

Output:

• Print "YES" if it is a lapindrome.

• Print "NO" otherwise.

Input Format:

• First line: integer T — number of test cases.

• Next T lines: each line contains a string S.

Output Format:

• For each test case, print YES or NO on its own line.

Constraints:

• 1 ≤ T ≤ 100

• 2 ≤ ∣S∣ ≤1000

• S consists only of lowercase English letters a–z.

Sample:

Input:

6

gaga

abcde

rotor

xyzxy

abbaab

ababc

Output:

YES

NO

YES

YES

NO

NO

Explanation:

1. gaga

• Length = 4 (even)

• Split → ga | ga

• Frequencies: {g:1, a:1} vs {g:1, a:1} → same → YES

2. abcde

• Length = 5 (odd)

• Split → ab | de (ignore middle c)

• Frequencies differ → NO

3. rotor

• Length = 5 (odd)

• Split → ro | or (ignore middle t)

• Frequencies: {r:1, o:1} vs {o:1, r:1} → same → YES

4. xyzxy

• Length = 5 → xy | xy → same → YES

5. abbaab

• Length = 6 (even)

• Split → abb | aab

• Left → {a:1, b:2}
  Right → {a:2, b:1} → not equal → NO

6. ababc

• Length = 5 (odd)

• Split → ab | bc → not equal → NO

Core Idea:

This is essentially an anagram check between the two halves.

Steps:

1. Split the string into two halves:

• Let n = |S|.

• If n is even:

• left = S[0 .. n/2 - 1]

• right = S[n/2 .. n-1]

• If n is odd:

• left = S[0 .. n/2 - 1]

• right = S[n/2 + 1 .. n-1] (skip middle character at index n/2)

2. Check if left and right are anagrams:

• Count frequency of each character in left and in right.

• If all 26 character frequencies match → YES.

• Else → NO.

Approach:

Algorithm:

For each string S:

1. Let n = length(S).

2. Define two frequency arrays freqL[26] and freqR[26] initialized to 0.

3. Determine split:

• If n is even:

• left indices: 0 to n/2 - 1

• right indices: n/2 to n-1

• If n is odd:

• left indices: 0 to n/2 - 1

• right indices: n/2 + 1 to n-1

4. For each character in the left half:

• freqL[ S[i] - 'a' ]++

5. For each character in the right half:

• freqR[ S[i] - 'a' ]++

6. Compare freqL and freqR:

• If all entries are equal → print "YES".

• Else → print "NO".

Time & Space Complexity:

For each test case:

• Time: O(n) to traverse string and compute frequencies.

• Space: O(1) (26-length arrays).

With T ≤ 100 and ∣S∣ ≤ 1000, this is very efficient.

Pseudocode:

Java code:

C code:

C++ code:

Python  code:

JavaScript code: