maximum-palindromes-after-operations

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 0-indexed string array <code>words</code> having length <code>n</code> and containing 0-indexed strings.

You are allowed to perform the following operation any number of times (including zero):

<ul>
	<li>Choose integers <code>i</code>, <code>j</code>, <code>x</code>, and <code>y</code> such that <code>0 &lt;= i, j &lt; n</code>, <code>0 &lt;= x &lt; words[i].length</code>, <code>0 &lt;= y &lt; words[j].length</code>, and swap the characters <code>words[i][x]</code> and <code>words[j][y]</code>.</li>
</ul>

Return an integer denoting the maximum number of palindromes <code>words</code> can contain, after performing some operations.

Note: <code>i</code> and <code>j</code> may be equal during an operation.

&nbsp;
Example 1:

<pre>
Input: words = [&quot;abbb&quot;,&quot;ba&quot;,&quot;aa&quot;]
Output: 3
Explanation: In this example, one way to get the maximum number of palindromes is:
Choose i = 0, j = 1, x = 0, y = 0, so we swap words[0][0] and words[1][0]. words becomes [&quot;bbbb&quot;,&quot;aa&quot;,&quot;aa&quot;].
All strings in words are now palindromes.
Hence, the maximum number of palindromes achievable is 3.</pre>

Example 2:

<pre>
Input: words = [&quot;abc&quot;,&quot;ab&quot;]
Output: 2
Explanation: In this example, one way to get the maximum number of palindromes is: 
Choose i = 0, j = 1, x = 1, y = 0, so we swap words[0][1] and words[1][0]. words becomes [&quot;aac&quot;,&quot;bb&quot;].
Choose i = 0, j = 0, x = 1, y = 2, so we swap words[0][1] and words[0][2]. words becomes [&quot;aca&quot;,&quot;bb&quot;].
Both strings are now palindromes.
Hence, the maximum number of palindromes achievable is 2.
</pre>

Example 3:

<pre>
Input: words = [&quot;cd&quot;,&quot;ef&quot;,&quot;a&quot;]
Output: 1
Explanation: In this example, there is no need to perform any operation.
There is one palindrome in words &quot;a&quot;.
It can be shown that it is not possible to get more than one palindrome after any number of operations.
Hence, the answer is 1.</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= words.length &lt;= 1000</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 100</code></li>
	<li><code>words[i]</code> consists only of lowercase English letters.</li>
</ul>

maxPalindromesAfterOperations

Maximum Palindromes After Operations

Valid Palindrome

valid-palindrome

验证回文串

Greedy

Array

Hash Table

String

Counting

Sorting

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

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

<ul>
	<li>选择整数<code>i</code>、<code>j</code>、<code>x</code>和<code>y</code>，满足<code>0 &lt;= i, j &lt; n</code>，<code>0 &lt;= x &lt; words[i].length</code>，<code>0 &lt;= y &lt; words[j].length</code>，交换 字符 <code>words[i][x]</code> 和 <code>words[j][y]</code> 。</li>
</ul>

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

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

&nbsp;

示例 1：

<pre>
输入：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 。
</pre>

示例 2：

<pre>
输入：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。
</pre>

示例 3：

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

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= words.length &lt;= 1000</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 100</code></li>
	<li><code>words[i]</code> 仅由小写英文字母组成。</li>
</ul>