Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/893.html

893. Groups of Special-Equivalent Strings (Easy)

You are given an array A of strings.

Two strings S and T are special-equivalent if after any number of moves, S == T.

A move consists of choosing two indices i and j with i % 2 == j % 2, and swapping S[i] with S[j].

Now, a group of special-equivalent strings from A is a non-empty subset S of A such that any string not in S is not special-equivalent with any string in S.

Return the number of groups of special-equivalent strings from A.

 

Example 1:

Input: ["a","b","c","a","c","c"]
Output: 3
Explanation: 3 groups ["a","a"], ["b"], ["c","c","c"]

Example 2:

Input: ["aa","bb","ab","ba"]
Output: 4
Explanation: 4 groups ["aa"], ["bb"], ["ab"], ["ba"]

Example 3:

Input: ["abc","acb","bac","bca","cab","cba"]
Output: 3
Explanation: 3 groups ["abc","cba"], ["acb","bca"], ["bac","cab"]

Example 4:

Input: ["abcd","cdab","adcb","cbad"]
Output: 1
Explanation: 1 group ["abcd","cdab","adcb","cbad"]

 

Note:

• 1 <= A.length <= 1000
• 1 <= A[i].length <= 20
• All A[i] have the same length.
• All A[i] consist of only lowercase letters.

Companies:
Facebook

Related Topics:
String

Solution 1.

• Java
• Python
• Go
• C++

• class Solution {
      public int numSpecialEquivGroups(String[] A) {
          Set<String> set = new HashSet<String>();
          for (String str : A) {
              int length = str.length();
              StringBuffer even = new StringBuffer();
              StringBuffer odd = new StringBuffer();
              for (int i = 0; i < length; i++) {
                  char c = str.charAt(i);
                  if (i % 2 == 0)
                      even.append(c);
                  else
                      odd.append(c);
              }
              char[] evenArray = even.toString().toCharArray();
              char[] oddArray = odd.toString().toCharArray();
              Arrays.sort(evenArray);
              Arrays.sort(oddArray);
              StringBuffer sorted = new StringBuffer();
              int evenLength = evenArray.length, oddLength = oddArray.length;
              int evenIndex = 0, oddIndex = 0;
              while (oddIndex < oddLength) {
                  sorted.append(evenArray[evenIndex++]);
                  sorted.append(oddArray[oddIndex++]);
              }
              if (evenIndex < evenLength)
                  sorted.append(evenArray[evenIndex++]);
              set.add(sorted.toString());
          }
          return set.size();
      }
  }
  
  ############
  
  class Solution {
      public int numSpecialEquivGroups(String[] words) {
          Set<String> s = new HashSet<>();
          for (String word : words) {
              s.add(convert(word));
          }
          return s.size();
      }
  
      private String convert(String word) {
          List<Character> a = new ArrayList<>();
          List<Character> b = new ArrayList<>();
          for (int i = 0; i < word.length(); ++i) {
              char ch = word.charAt(i);
              if (i % 2 == 0) {
                  a.add(ch);
              } else {
                  b.add(ch);
              }
          }
          Collections.sort(a);
          Collections.sort(b);
          StringBuilder sb = new StringBuilder();
          for (char c : a) {
              sb.append(c);
          }
          for (char c : b) {
              sb.append(c);
          }
          return sb.toString();
      }
  }
  

• class Solution:
      def numSpecialEquivGroups(self, words: List[str]) -> int:
          s = {''.join(sorted(word[::2]) + sorted(word[1::2])) for word in words}
          return len(s)
  
  ############
  
  class Solution(object):
      def numSpecialEquivGroups(self, A):
          """
          :type A: List[str]
          :rtype: int
          """
          B = set()
          for a in A:
              B.add(''.join(sorted(a[0::2])) + ''.join(sorted(a[1::2])))
          return len(B)
  

• func numSpecialEquivGroups(words []string) int {
  	s := map[string]bool{}
  	for _, word := range words {
  		a, b := []rune{}, []rune{}
  		for i, c := range word {
  			if i&1 == 1 {
  				a = append(a, c)
  			} else {
  				b = append(b, c)
  			}
  		}
  		sort.Slice(a, func(i, j int) bool {
  			return a[i] < a[j]
  		})
  		sort.Slice(b, func(i, j int) bool {
  			return b[i] < b[j]
  		})
  		s[string(a)+string(b)] = true
  	}
  	return len(s)
  }
  

• class Solution {
  public:
      int numSpecialEquivGroups(vector<string>& words) {
          unordered_set<string> s;
          for (auto& word : words) {
              string a = "", b = "";
              for (int i = 0; i < word.size(); ++i) {
                  if (i & 1)
                      a += word[i];
                  else
                      b += word[i];
              }
              sort(a.begin(), a.end());
              sort(b.begin(), b.end());
              s.insert(a + b);
          }
          return s.size();
      }
  };
  

All Problems

All Solutions