Question

2531. Make Number of Distinct Characters Equal

中文文档

Description

You are given two 0-indexed strings word1 and word2.

A move consists of choosing two indices i and j such that 0 <= i < word1.length and 0 <= j < word2.length and swapping word1[i] with word2[j].

Return true _if it is possible to get the number of distinct characters in_ word1 _and_ word2 _to be equal with exactly one move. _Return false _otherwise_.

 

Example 1:

Input: word1 = "ac", word2 = "b"
Output: false
Explanation: Any pair of swaps would yield two distinct characters in the first string, and one in the second string.

Example 2:

Input: word1 = "abcc", word2 = "aab"
Output: true
Explanation: We swap index 2 of the first string with index 0 of the second string. The resulting strings are word1 = "abac" and word2 = "cab", which both have 3 distinct characters.

Example 3:

Input: word1 = "abcde", word2 = "fghij"
Output: true
Explanation: Both resulting strings will have 5 distinct characters, regardless of which indices we swap.

 

Constraints:

• 1 <= word1.length, word2.length <= 105
• word1 and word2 consist of only lowercase English letters.

Solutions

Solution 1

class Solution:
  def isItPossible(self, word1: str, word2: str) -> bool:
    cnt1 = [0] * 26
    cnt2 = [0] * 26
    for c in word1:
      cnt1[ord(c) - ord('a')] += 1
    for c in word2:
      cnt2[ord(c) - ord('a')] += 1
    for i, a in enumerate(cnt1):
      for j, b in enumerate(cnt2):
        if a and b:
          cnt1[i], cnt2[j] = cnt1[i] - 1, cnt2[j] - 1
          cnt1[j], cnt2[i] = cnt1[j] + 1, cnt2[i] + 1
          if sum(v > 0 for v in cnt1) == sum(v > 0 for v in cnt2):
            return True
          cnt1[i], cnt2[j] = cnt1[i] + 1, cnt2[j] + 1
          cnt1[j], cnt2[i] = cnt1[j] - 1, cnt2[i] - 1
    return False

class Solution {
  public boolean isItPossible(String word1, String word2) {
    int[] cnt1 = new int[26];
    int[] cnt2 = new int[26];
    for (int i = 0; i < word1.length(); ++i) {
      ++cnt1[word1.charAt(i) - 'a'];
    }
    for (int i = 0; i < word2.length(); ++i) {
      ++cnt2[word2.charAt(i) - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
      for (int j = 0; j < 26; ++j) {
        if (cnt1[i] > 0 && cnt2[j] > 0) {
          --cnt1[i];
          --cnt2[j];
          ++cnt1[j];
          ++cnt2[i];
          int d = 0;
          for (int k = 0; k < 26; ++k) {
            if (cnt1[k] > 0) {
              ++d;
            }
            if (cnt2[k] > 0) {
              --d;
            }
          }
          if (d == 0) {
            return true;
          }
          ++cnt1[i];
          ++cnt2[j];
          --cnt1[j];
          --cnt2[i];
        }
      }
    }
    return false;
  }
}

class Solution {
public:
  bool isItPossible(string word1, string word2) {
    int cnt1[26]{};
    int cnt2[26]{};
    for (char& c : word1) {
      ++cnt1[c - 'a'];
    }
    for (char& c : word2) {
      ++cnt2[c - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
      for (int j = 0; j < 26; ++j) {
        if (cnt1[i] > 0 && cnt2[j] > 0) {
          --cnt1[i];
          --cnt2[j];
          ++cnt1[j];
          ++cnt2[i];
          int d = 0;
          for (int k = 0; k < 26; ++k) {
            if (cnt1[k] > 0) {
              ++d;
            }
            if (cnt2[k] > 0) {
              --d;
            }
          }
          if (d == 0) {
            return true;
          }
          ++cnt1[i];
          ++cnt2[j];
          --cnt1[j];
          --cnt2[i];
        }
      }
    }
    return false;
  }
};

func isItPossible(word1 string, word2 string) bool {
  cnt1 := [26]int{}
  cnt2 := [26]int{}
  for _, c := range word1 {
    cnt1[c-'a']++
  }
  for _, c := range word2 {
    cnt2[c-'a']++
  }
  for i := range cnt1 {
    for j := range cnt2 {
      if cnt1[i] > 0 && cnt2[j] > 0 {
        cnt1[i], cnt2[j] = cnt1[i]-1, cnt2[j]-1
        cnt1[j], cnt2[i] = cnt1[j]+1, cnt2[i]+1
        d := 0
        for k, a := range cnt1 {
          if a > 0 {
            d++
          }
          if cnt2[k] > 0 {
            d--
          }
        }
        if d == 0 {
          return true
        }
        cnt1[i], cnt2[j] = cnt1[i]+1, cnt2[j]+1
        cnt1[j], cnt2[i] = cnt1[j]-1, cnt2[i]-1
      }
    }
  }
  return false
}