Domain 1EasyCORE

Groups of Special-Equivalent Strings

The problem requires us to determine the number of groups of special-equivalent strings from an array `A` of strings. Two strings are considered special-equivalent if they can be transformed into each other by swapping any two even-indexed characters or any two odd-indexed characters any number of times.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

893. Groups of Special-Equivalent Strings

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 69.6%


Problem Breakdown

The problem requires us to determine the number of groups of special-equivalent strings from an array A of strings. Two strings are considered special-equivalent if they can be transformed into each other by swapping any two even-indexed characters or any two odd-indexed characters any number of times.

Inputs:

  • An array A of strings, where each string consists of lowercase letters.
  • All strings in the array have the same length.

Outputs:

  • The number of groups of special-equivalent strings.

Implicit Constraints/Edge Cases:

  • If the input array is empty, the output should be 0.
  • Strings with different lengths are not considered (though this is already handled by the problem constraints).
  • Strings that are identical are trivially special-equivalent.

Intuition

A brute-force approach would involve checking each pair of strings to see if they are special-equivalent, which would result in a time complexity of O(n^2 * m), where n is the number of strings and m is the length of each string. This is inefficient for larger inputs.

The key insight is that two strings are special-equivalent if and only if their even-indexed characters can be rearranged to match the even-indexed characters of the other string, and similarly for their odd-indexed characters. Therefore, we can use this property to group strings by sorting their even and odd indexed characters separately.

Approach

  1. Initialize a Set for Groups: Use a set to store unique groups of special-equivalent strings.
  2. Iterate Over Each String in the Array:
    • For each string, separate its characters into two lists: one for even-indexed characters and another for odd-indexed characters.
    • Sort both lists.
  3. Create a Canonical Form: Concatenate the sorted even-indexed list and the sorted odd-indexed list to form a canonical representation of the string.
  4. Add to Set: Add this canonical form to the set. Since sets automatically handle duplicates, each unique canonical form represents a distinct group of special-equivalent strings.
  5. Return the Size of the Set: The size of the set gives the number of groups.

Complexity Analysis

  • Time Complexity: O(n * m log m), where n is the number of strings and m is the length of each string. Sorting each list takes O(m log m) time, and we do this for each of the n strings.
  • Space Complexity: O(n * m), as we store a canonical form for each string in the set.

Solution

def numSpecialEquivGroups(A):
    groups = set()
    
    for s in A:
        even_chars = sorted(s[::2])
        odd_chars = sorted(s[1::2])
        canonical_form = ''.join(even_chars) + ''.join(odd_chars)
        groups.add(canonical_form)
    
    return len(groups)

# Example usage:
A1 = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
print(numSpecialEquivGroups(A1))  # Output: 3

A2 = ["abc","acb","bac","bca","cab","cba"]
print(numSpecialEquivGroups(A2))  # Output: 3

Edge Cases Handled

  • Empty Input: If the input array is empty, the function returns 0 because there are no strings to group.
  • Identical Strings: Identical strings are trivially special-equivalent and will be grouped together.
  • Strings with Different Lengths: The problem constraints ensure all strings have the same length, so this case does not need to be handled.