1328 破坏回文串

· 2025-3-5   · 次阅读   · 字数统计: 179字   · 阅读时长≈ 1分钟

  · 算法题解   · LeetCode

题目链接

1328. 破坏回文串

分析

对于长度为 $1$ 的串来说，必定为回文串，直接返回空串即可

对于其余回文串来说，找到第一个不等于 $a$ 的字母修改为 $a$ 时字典序最小

如果回文串除中心外出现全是 $a$ 的情况，将最后一位修改为 $b$ 时字典序最小

代码实现

class Solution {
public:
    string breakPalindrome(string palindrome) {
        int n = palindrome.size();
        if(n == 1)
            return "";
  
        for(int i = 0; i < n >> 1; ++i) {
            if(palindrome[i] != 'a') {
                palindrome[i] = 'a';
                return palindrome;
            }    
        }
  
        palindrome[n - 1] = 'b';
        return palindrome;
    }
};

复杂度分析

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$