本文涉及知识点

C++贪心
字符串 树状数组 分类讨论

LeetCode2193. 得到回文串的最少操作次数

给你一个只包含小写英文字母的字符串 s 。
每一次 操作 ，你可以选择 s 中两个 相邻 的字符，并将它们交换。
请你返回将 s 变成回文串的 最少操作次数 。
注意 ，输入数据会确保 s 一定能变成一个回文串。
示例 1：
输入：s = “aabb”
输出：2
解释：
我们可以将 s 变成 2 个回文串，“abba” 和 “baab” 。

• 我们可以通过 2 次操作得到 “abba” ：“aabb” -> “abab” -> “abba” 。
• 我们可以通过 2 次操作得到 “baab” ：“aabb” -> “abab” -> “baab” 。
  因此，得到回文串的最少总操作次数为 2 。
  示例 2：
  输入：s = “letelt”
  输出：2
  解释：
  通过 2 次操作从 s 能得到回文串 “lettel” 。
  其中一种方法是：“letelt” -> “letetl” -> “lettel” 。
  其他回文串比方说 “tleelt” 也可以通过 2 次操作得到。
  可以证明少于 2 次操作，无法得到回文串。
  提示：
  1 <= s.length <= 2000
  s 只包含小写英文字母。
  s 可以通过有限次操作得到一个回文串。

贪心

s[0]和s[n-1]是第0对，s[1]和s[n-2]是第二对…
从大到小处理第i对，会让已经处理好的对，不在匹配。故只能从小到大处理。

分类讨论

任意两对x和y，有如下关系：
一,xxyy，两者相互无影响。
二， ⋯ a 个字符 x ⋯ b 个字符 y ⋯ c 个字符 y ⋯ d 个字符 x ⋯ e 个字符 ^{a个字符}_{\cdots} x ^{b个字符}_{\cdots}y ^{c个字符}_{\cdots}y ^{d个字符}_{\cdots}x ^{e个字符}_{\cdots} ⋯a个字符​x⋯b个字符​y⋯c个字符​y⋯d个字符​x⋯e个字符​
先处理x，需要：a+e 在处理y，需要:a+b+d+e
先处理y:需要a+b+1+d+e+1,再处理x需要：a+e。
必须先处理x。
三， ⋯ a 个字符 x ⋯ b 个字符 y ⋯ c 个字符 x ⋯ d 个字符 y ⋯ e 个字符 ^{a个字符}_{\cdots} x ^{b个字符}_{\cdots}y ^{c个字符}_{\cdots}x ^{d个字符}_{\cdots}y ^{e个字符}_{\cdots} ⋯a个字符​x⋯b个字符​y⋯c个字符​x⋯d个字符​y⋯e个字符​
先处理x: a+d+e+1，再处理y: a+b+e
线处理y: a+b+1+e 再处理x:a+d+e
结果一样：先处理谁都可以。
结果： 除非被另外一个字符包括，则可以先处理。
最左边的x，如果有多个可以匹配的x，选择最右边的x。
F o r i : 0 i < s . l e n g t h / 2 匹配 s [ i ] For\Large_{i:0}^{i < s.length/2}匹配s[i] Fori:0i<s.length/2​匹配s[i]
如果s[i] 是只有一个，按就是中心。从后面处理，将s转置。
以可以忽略，留到最后处理：

	if (0 == index)
			{
				iRet += s.length()/2;
                s = s.substr(1);
				continue;
			}

代码

核心代码

class Solution {
public:
	int minMovesToMakePalindrome(string s) {
		int iRet = 0;
		while (s.length() > 2)
		{
			int index = s.find_last_of(s[0]);
			if (0 == index)
			{
				std::reverse(s.begin(), s.end());
				continue;
			}
			iRet += (s.length() - 1 - index);
			s = s.substr(1, index - 1) + s.substr(index + 1);
		}
		return iRet;
	}
};

测试用例

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	string s ;
	{
		Solution sln;
		s = "adabb";
		auto res = sln.minMovesToMakePalindrome(s);
		Assert(3, res);
	}
	
	
}

2023 年 3月版

class Solution {
public:
int minMovesToMakePalindrome(string s) {
//统计各字符出行的次数
std::unordered_map<char, int> mFreq;
for (const auto&ch : s)
{
mFreq[ch]++;
}
int iRet = 0;
//记录组间移动后各字符的位置
std::unordered_map<char, vector> mLeft, mRight;
int iLeftCnt = 0, iRightCnt = 0;
for (int i = 0; i < s.length(); i++)
{
const char& ch = s[i];
if (mLeft[ch].size() < mFreq[ch] / 2)
{
iRet += i - iLeftCnt;//组间移动
mLeft[ch].emplace_back(iLeftCnt);
iLeftCnt++;
}
else
{
mRight[ch].emplace_back(iRightCnt);
iRightCnt++;
}
}
//如果是奇数，左边末尾加上
for (auto& it : mLeft)
{
if (mFreq[it.first] & 1)
{
it.second.emplace_back(iLeftCnt++);
}
}
//vMove[i]的值是b，表示目前在i位置的字符要移动到b位置
vector vMove(iRightCnt);
for (auto it : mRight)
{
const auto& vLeft = mLeft[it.first];
for (int i = 0; i < it.second.size(); i++)
{
const int j = vLeft.size() - 1 - i;
const int iNewPos = iRightCnt -1 - vLeft[j];
vMove[it.second[i]] = iNewPos;
}
}

	//逆序对数就是组间移动数
	CTreeArr<int> tree(iRightCnt);
	for (int i = iRightCnt - 1; i >= 0; i--)
	{
		iRet += tree.Sum(vMove[i]);
		tree.Add(vMove[i], 1);
	}
	return iRet;
}

};

2023年7月版

class Solution {
public:
int minMovesToMakePalindrome(string s) {
m_c = s.length();
int iRet = 0;
for (int left = 0; left < m_c / 2; left++)
{
int right = s.length() - 1;
for (; s[right] != s[left]; right–);
if (left == right)
{
iRet += m_c / 2 - left;
}
else
{
iRet += s.length() - 1 - right;
s.erase(right, 1);
}
}
return iRet;
}
int m_c;
}