题解 | #牛群密码 - 有效回文# 回文串

知识点

回文字符串 哈希表

思路

首先用哈希表对字符串去重，如果个数大于k则返回false

其次开始判断是否是回文串（有一个容错），如果发现不能相等的时候，应该分别去除掉不相等的那对中的一个字符后再进行正常的回文串判断。

因为只会判断一次，所以时间复杂度是的

注意当出现不一样的时候根据是否和下一个位置是否相等选择一个继续判断回文串的思路是错误的。因为可能存在“abab”这样的字符串，即当出现第一个a和最后一个b不等的时候，把左指针右移和右指针左移都可以继续相等时，不能擅自选一个方向移动。

例如hack数据：

"abccbab",10

"abaccab",10

目前我在时间榜上的代码也是错误的; 但是后续更新牛客无法更新到榜上 很无语

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param password string字符串 
     * @param k int整型 
     * @return bool布尔型
     */
    bool isValidPalindrome(string password, int k) {
        unordered_set<char> S(password.begin(), password.end());
        if (S.size() > k) return false;
        for (int i = 0, j = password.size() - 1; i < j; i ++, j --) {
            if (password[i] == password[j]) continue;
            return check(password, i + 1, j) or check(password, i, j - 1);
        }
        return true;
    }
    bool check(const string& s, int l, int r) {
        if (l > r) return false;
        for (int i = l, j = r; i < j; i ++, j --) {
            if (s[i] != s[j]) return false;
        }
        return true;
    }
};