Question

3035. 回文字符串的最大数量

English Version

题目描述

给你一个下标从 0 开始的字符串数组 words ，数组的长度为 n ，且包含下标从 0 开始的若干字符串。

你可以执行以下操作 任意 次数（包括零次）：

• 选择整数i、j、x和y，满足0 <= i, j < n，0 <= x < words[i].length，0 <= y < words[j].length，交换 字符 words[i][x] 和 words[j][y] 。

返回一个整数，表示在执行一些操作后，words 中可以包含的回文串的 最大 数量。

注意：在操作过程中，i 和 j 可以相等。

 

示例 1：

输入：words = ["abbb","ba","aa"]
输出：3
解释：在这个例子中，获得最多回文字符串的一种方式是：
选择 i = 0, j = 1, x = 0, y = 0，交换 words[0][0] 和 words[1][0] 。words 变成了 ["bbbb","aa","aa"] 。
words 中的所有字符串都是回文。
因此，可实现的回文字符串的最大数量是 3 。

示例 2：

输入：words = ["abc","ab"]
输出：2
解释：在这个例子中，获得最多回文字符串的一种方式是： 
选择 i = 0, j = 1, x = 1, y = 0，交换 words[0][1] 和 words[1][0] 。words 变成了 ["aac","bb"] 。
选择 i = 0, j = 0, x = 1, y = 2，交换 words[0][1] 和 words[0][2] 。words 变成了 ["aca","bb"] 。
两个字符串都是回文 。
因此，可实现的回文字符串的最大数量是 2。

示例 3：

输入：words = ["cd","ef","a"]
输出：1
解释：在这个例子中，没有必要执行任何操作。
words 中有一个回文 "a" 。
可以证明，在执行任何次数操作后，无法得到更多回文。
因此，答案是 1 。

 

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 100
• words[i] 仅由小写英文字母组成。

解法

方法一

class Solution:
  def maxPalindromesAfterOperations(self, words: List[str]) -> int:
    s = mask = 0
    for w in words:
      s += len(w)
      for c in w:
        mask ^= 1 << (ord(c) - ord("a"))
    s -= mask.bit_count()
    words.sort(key=len)
    ans = 0
    for w in words:
      s -= len(w) // 2 * 2
      if s < 0:
        break
      ans += 1
    return ans

class Solution {
  public int maxPalindromesAfterOperations(String[] words) {
    int s = 0, mask = 0;
    for (var w : words) {
      s += w.length();
      for (var c : w.toCharArray()) {
        mask ^= 1 << (c - 'a');
      }
    }
    s -= Integer.bitCount(mask);
    Arrays.sort(words, (a, b) -> a.length() - b.length());
    int ans = 0;
    for (var w : words) {
      s -= w.length() / 2 * 2;
      if (s < 0) {
        break;
      }
      ++ans;
    }
    return ans;
  }
}

class Solution {
public:
  int maxPalindromesAfterOperations(vector<string>& words) {
    int s = 0, mask = 0;
    for (const auto& w : words) {
      s += w.length();
      for (char c : w) {
        mask ^= 1 << (c - 'a');
      }
    }
    s -= __builtin_popcount(mask);
    sort(words.begin(), words.end(), [](const string& a, const string& b) { return a.length() < b.length(); });
    int ans = 0;
    for (const auto& w : words) {
      s -= w.length() / 2 * 2;
      if (s < 0) {
        break;
      }
      ++ans;
    }
    return ans;
  }
};

func maxPalindromesAfterOperations(words []string) (ans int) {
  var s, mask int
  for _, w := range words {
    s += len(w)
    for _, c := range w {
      mask ^= 1 << (c - 'a')
    }
  }
  s -= bits.OnesCount(uint(mask))
  sort.Slice(words, func(i, j int) bool {
    return len(words[i]) < len(words[j])
  })
  for _, w := range words {
    s -= len(w) / 2 * 2
    if s < 0 {
      break
    }
    ans++
  }
  return
}

function maxPalindromesAfterOperations(words: string[]): number {
  let s: number = 0;
  let mask: number = 0;
  for (const w of words) {
    s += w.length;
    for (const c of w) {
      mask ^= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
    }
  }
  s -= (mask.toString(2).match(/1/g) || []).length;
  words.sort((a, b) => a.length - b.length);
  let ans: number = 0;
  for (const w of words) {
    s -= Math.floor(w.length / 2) * 2;
    if (s < 0) {
      break;
    }
    ans++;
  }
  return ans;
}