小旭讲解 LeetCode 1542. 找出最长的超赞子字符串
文章目录

  • 原题
  • 思路 – 动态规划 & 状态压缩
  • 代码
  • 参考

原题

给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。

「超赞子字符串」需满足满足下述两个条件:

该字符串是 s 的一个非空子字符串
进行任意次数的字符交换后,该字符串可以变成一个回文字符串

示例 1:

输入:s = “3242415”
输出:5
解释:”24241″ 是最长的超赞子字符串,交换其中的字符后,可以得到回文 “24142”

示例 2:

输入:s = “12345678”
输出:1

示例 3:

输入:s = “213123”
输出:6
解释:”213123″ 是最长的超赞子字符串,交换其中的字符后,可以得到回文 “231132”

示例 4:

输入:s = “00”
输出:2
 

提示:

  • 1 <= s.length <= 10^5
  • s 仅由数字组成

思路 – 动态规划 & 状态压缩

分析回文串的特性:如果 S 是回文字符串,那么所有字符中,出现的次数为奇数的最多只有一种字符。如:

S = “1231233” // 只有一个字符 c 的出现次数为奇数

S = “123123” // 没有任何一个字符的出现次数为奇数

利用这个特性,通过状态压缩 —— 以二进制位表示字符串中字符出现的奇偶性。如:(1001)_2代表,字符 “0” 与 “3” 出现的次数为奇数,字符 “1” 与 “2” 出现的次数为偶数(或者没有出现过),处理字符串中所有前缀的状态。

每一个前缀字符串压缩成一个状态作为 Key,其 Value 为当前状态在字符串中出现的位置索引最小的一个值(利用其可以计算长度)。

当处理一个前缀字符串时,它的状态会有如下几种情况:

  • 出现次数为奇数的字符小于等于 1 次,那么当前前缀字符串即可组成回文字符串
  • 出现次数为奇数的字符大于 1 次
    • 枚举任意一个字符,让其出现过的次数为奇数,通过前缀数组进行计算最大的长度

代码

class Solution { public:     int longestAwesome(string s) {         int cnt[1 << 10];         memset(cnt, 0x3f, sizeof cnt);         int last = 0, ans = 0;         cnt[0] = -1;         for (int i = 0; i < s.size(); ++i) {             last ^= (1 << (s[i] - '0'));             int bcnt = 0;             for (int j = 0; j < 10; ++j) {                 if ((last & (1 << j)) > 0) ++bcnt;             }             if (bcnt <= 1) {                 ans = max(ans, i - cnt[0]);             } else {                 for (int j = 0; j < 10; ++j) {                     int nlast = last ^ (1 << j);                     ans = max(ans, i - cnt[nlast]);                 }             }             if (cnt[last] == 0x3f3f3f3f) cnt[last] = i;         }         return ans;     } };
class Solution { public:     int longestAwesome(string s) {         int cnt[1 << 10], last = 0, ans = 0;         memset(cnt, 0x3f, sizeof cnt);         cnt[0] = -1;         for (int i = 0; i < s.size(); ++i) {             last ^= (1 << (s[i] - '0'));             for (int j = 0; j < 10; ++j) {                 int nlast = last ^ (1 << j);                 ans = max(ans, i - cnt[nlast]);             }             cnt[last] = min(cnt[last], i);             ans = max(ans, i - cnt[last]);         }         return ans;     } };

复杂度分析

时间复杂度:O(K * N) K 为字符种类,N为字符长度
空间复杂度:O(2 ^ K)

参考

[1]. LeetCode 原题. https://leetcode-cn.com/problems/find-longest-awesome-substring

小旭讲解 LeetCode 1542. 找出最长的超赞子字符串leetcode刷题题解部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 小旭讲解 LeetCode 1542. 找出最长的超赞子字符串leetcode刷题题解