893. Groups of Special-Equivalent Strings

Problem Statement

link: LeetCode.cn LeetCode You are given an array of strings of the same length words.

In one move, you can swap any two even indexed characters or any two odd indexed characters of a string words[i].

Two strings words[i] and words[j] are special-equivalent if after any number of moves, words[i] == words[j].

For example, words[i] = “zzxy” and words[j] = “xyzz” are special-equivalent because we may make the moves “zzxy” -> “xzzy” -> “xyzz”. A group of special-equivalent strings from words is a non-empty subset of words such that:

Every pair of strings in the group are special equivalent, and The group is the largest size possible (i.e., there is not a string words[i] not in the group such that words[i] is special-equivalent to every string in the group). Return the number of groups of special-equivalent strings from words.

Example:

Input: words = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"] Output: 3

Input: words = ["abc","acb","bac","bca","cab","cba"] Output: 3

Constraints: 1 <= words.length <= 1000 1 <= words[i].length <= 20 words[i] consist of lowercase English letters. All the strings are of the same length.

Solution Approach

To solve this problem, categorize each string by creating a tuple that represents the frequency of characters at even and odd indices, then count the number of unique tuples to determine the number of special-equivalent groups.

Algorithm

1. Character Frequency Counting: For each string, create a frequency tuple for characters at even indices and odd indices separately, then combine these counts into a single tuple.
2. Unique Tuple Representation: Use a set to collect these tuples for all strings, as each unique tuple represents a distinct group of special-equivalent strings.
3. Group Count: The number of unique tuples in the set corresponds to the number of special-equivalent groups in the input list of strings.

Implement

    class Solution:
    def numSpecialEquivGroups(self, words: List[str]) -> int:
        def count(word):
            ans = [0] * 52
            for i, letter in enumerate(word):
                ans[ord(letter) - ord('a') + 26 * (i % 2)] += 1
            return tuple(ans)
        
        return len({count(word) for word in words})
        
    def encode(word):
              even_chars = sorted(word[::2])  # Characters at even indices
              odd_chars = sorted(word[1::2])  # Characters at odd indices
              return ''.join(even_chars) + ''.join(odd_chars)  # Concatenate the sorted characters
          
          q =   {encode(word) for word in words}
          print(q)
          return len(q)
     

    
    

Twitter  facebook  Email