Formatted question description: https://leetcode.ca/all/1328.html

1328. Break a Palindrome (Medium)

Given a palindromic string palindrome, replace exactly one character by any lowercase English letter so that the string becomes the lexicographically smallest possible string that isn't a palindrome.

After doing so, return the final string.  If there is no way to do so, return the empty string.

 

Example 1:

Input: palindrome = "abccba"
Output: "aaccba"

Example 2:

Input: palindrome = "a"
Output: ""

 

Constraints:

  • 1 <= palindrome.length <= 1000
  • palindrome consists of only lowercase English letters.

Related Topics:
String

Solution 1.

// OJ: https://leetcode.com/problems/break-a-palindrome/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    string breakPalindrome(string palindrome) {
        int N = palindrome.size(), end = N / 2;
        for (int i = 0; i < end; ++i) {
            if (palindrome[i] != 'a') {
                palindrome[i] = 'a';
                return palindrome;
            }
        }
        if (N > 1) {
            palindrome[N - 1] = 'b';
            return palindrome;
        }
        return "";
    }
};

Java

  • class Solution {
        public String breakPalindrome(String palindrome) {
            char[] array = palindrome.toCharArray();
            int length = array.length;
            if (length == 1)
                return "";
            int halfMax = length / 2;
            for (int i = 0; i < halfMax; i++) {
                char c = array[i];
                if (c != 'a') {
                    array[i] = 'a';
                    return new String(array);
                }
            }
            array[length - 1] = 'b';
            return new String(array);
        }
    }
    
  • // OJ: https://leetcode.com/problems/break-a-palindrome/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        string breakPalindrome(string s) {
            int N = s.size();
            if (N == 1) return "";
            for (int i = 0, end = N / 2; i < end; ++i) {
                if (s[i] != 'a') {
                    s[i] = 'a';
                    return s;
                }
            }
            s[N - 1] = 'b';
            return s;
        }
    };
    
  • print("Todo!")
    

All Problems

All Solutions