Medium

题目描述

给你一个由小写英文字母组成的回文字符串 palindrome，请你将其中 恰好一个 字符用任意小写英文字母替换，使得结果字符串 不是 回文串，且字典序尽可能小。

请你返回结果字符串。如果无法做到，则返回一个 空字符串 。

如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符严格小于 b 中的对应字符。例如，"abcc" 字典序比 "abcd" 小，因为不同的第一个位置是在第四个字符，'c' < 'd' 。

示例 1：

输入：palindrome = "abccba"
输出："aaccba"
解释：存在多种方法可以使 "abccba" 不是回文，例如 "zbccba", "aaccba", 和 "abacba" 。
在所有方法中，"aaccba" 的字典序最小。

示例 2：

输入：palindrome = "a"
输出：""
解释：不存在替换一个字符使 "a" 变成非回文的方法，所以返回空字符串。

提示：

  • 1 <= palindrome.length <= 1000
  • palindrome 只包含小写英文字母。

解题思路

这是一个贪心算法问题。要使修改后的字符串字典序最小且不是回文，我们需要考虑以下策略：

核心思路：

  1. 特殊情况处理：如果字符串长度为1，无论怎么修改都无法破坏回文性质，返回空字符串。

  2. 贪心策略：为了获得字典序最小的结果，我们应该尽可能从左边开始修改字符。

    • 遍历字符串的前半部分（不包括中心字符）
    • 找到第一个不是 ‘a’ 的字符，将其改为 ‘a’
    • 这样既破坏了回文性质，又保证了字典序最小

  3. 全是 ‘a’ 的情况：如果字符串全部由 ‘a’ 组成，那么前面的策略无效。此时我们只能修改最后一个字符为 ‘b’，这样可以保证字典序尽可能小。

算法步骤：

  • 首先检查长度是否为1
  • 遍历前半部分，寻找第一个非 ‘a’ 字符并替换为 ‘a’
  • 如果没找到，说明全是 ‘a’，将最后一个字符改为 ‘b’

时间复杂度为O(n)，空间复杂度为O(1)（不考虑结果字符串的空间）。

代码实现

class Solution {
public:
    string breakPalindrome(string palindrome) {
        int n = palindrome.length();
        if (n == 1) return "";
        
        // 尝试将前半部分的第一个非'a'字符改为'a'
        for (int i = 0; i < n / 2; i++) {
            if (palindrome[i] != 'a') {
                palindrome[i] = 'a';
                return palindrome;
            }
        }
        
        // 如果全是'a'，将最后一个字符改为'b'
        palindrome[n - 1] = 'b';
        return palindrome;
    }
};

class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        n = len(palindrome)
        if n == 1:
            return ""
        
        palindrome = list(palindrome)
        
        # 尝试将前半部分的第一个非'a'字符改为'a'
        for i in range(n // 2):
            if palindrome[i] != 'a':
                palindrome[i] = 'a'
                return ''.join(palindrome)
        
        # 如果全是'a'，将最后一个字符改为'b'
        palindrome[n - 1] = 'b'
        return ''.join(palindrome)

public class Solution {
    public string BreakPalindrome(string palindrome) {
        int n = palindrome.Length;
        if (n == 1) return "";
        
        char[] chars = palindrome.ToCharArray();
        
        // 尝试将前半部分的第一个非'a'字符改为'a'
        for (int i = 0; i < n / 2; i++) {
            if (chars[i] != 'a') {
                chars[i] = 'a';
                return new string(chars);
            }
        }
        
        // 如果全是'a'，将最后一个字符改为'b'
        chars[n - 1] = 'b';
        return new string(chars);
    }
}

/**
 * @param {string} palindrome
 * @return {string}
 */
var breakPalindrome = function(palindrome) {
    if (palindrome.length === 1) return "";
    
    let arr = palindrome.split('');
    let n = arr.length;
    
    for (let i = 0; i < Math.floor(n / 2); i++) {
        if (arr[i] !== 'a') {
            arr[i] = 'a';
            return arr.join('');
        }
    }
    
    arr[n - 1] = 'b';
    return arr.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n)，其中 n 是字符串长度，最多遍历字符串一次
空间复杂度O(1)，除了存储结果所需的空间外，只使用常量级额外空间