原文链接: https://leetcode-cn.com/problems/find-longest-awesome-substring

英文原文

Given a string s. An awesome substring is a non-empty substring of s such that we can make any number of swaps in order to make it palindrome.

Return the length of the maximum length awesome substring of s.

 

Example 1:

Input: s = "3242415"
Output: 5
Explanation: "24241" is the longest awesome substring, we can form the palindrome "24142" with some swaps.

Example 2:

Input: s = "12345678"
Output: 1

Example 3:

Input: s = "213123"
Output: 6
Explanation: "213123" is the longest awesome substring, we can form the palindrome "231132" with some swaps.

Example 4:

Input: s = "00"
Output: 2

 

Constraints:

• 1 <= s.length <= 105
• s consists only of digits.

中文题目

给你一个字符串 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 仅由数字组成

通过代码

高赞题解

解题思路：

1. 超赞字符串的条件：一个字符串可以重新排序得到一个回文字符串的充要条件是：对字符计数，出现奇数次的字符个数小于等于 $1$。

   abcba
   abba

2. 状态压缩：因为只关心一个字符出现的次数是奇是偶，因此不需要真正的计数，可用1表示出现奇数次，$0$ 表示出现偶数次，更进一步，数字只有 $0-9$ 一共 $10$个，可以进行状态压缩。用 status记录，status&(1<<i)表示i出现的奇偶。

   那么数字 i 的数量 +1 即可表示为：

   status=stauts^(1<<i); //0^1=1 1^1=0

3. 前缀和：记录每个 status 出现的最左位置

   map<status,index>

   1. 如果 status2 和 status1 相同，那么区间 (map.get(status1),map.get(status2)] 中所有数字都出现了偶数次，满足超赞的条件。
   2. 如果 status2 和 status1 只差一位不同，那么区间 (map.get(status1),map.get(status2)] 中有一个数字出现了奇数次，其余数字都出现了偶数次，满足超赞的条件。

   按照条件枚举即可。

代码：

[]
class Solution {
    public int longestAwesome(String s) {
        HashMap<Integer,Integer> map=new HashMap<>();
        int cur=0;  //状态
        int ans=1;  //记录答案
        map.put(cur,-1); 
        for(int c=0;c<s.length();c++){
            int ch=s.charAt(c)-'0';
            //计数
            cur=cur^(1<<ch);
            //一个数字出现奇数次，其余出现偶数次
            for(int i=0;i<10;i++){
                int next=cur^(1<<i);
                if(map.containsKey(next)){
                    ans=Math.max(ans,c-map.get(next));
                }
            }
            //所有都出现了偶数次
            if(!map.containsKey(cur)){
                map.put(cur,c);
            }else{
                ans=Math.max(ans,c-map.get(cur));
            }
        }
        return ans;
    }
}

欢迎讨论

统计信息

通过次数	提交次数	AC比率
2593	6702	38.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言