# Break a Palindrome
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/break-a-palindrome)
Canonical: https://scaleengineer.com/dsa/problems/break-a-palindrome
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
**Companies:** [Expedia](https://scaleengineer.com/companies/expedia), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Nvidia](https://scaleengineer.com/companies/nvidia), [VMware](https://scaleengineer.com/companies/vmware), [MathWorks](https://scaleengineer.com/companies/mathworks)
---
## Problem
Given a palindromic string of lowercase English letters `palindrome`, replace **exactly one** character with any lowercase English letter so that the resulting string is **not** a palindrome and that it is the **lexicographically smallest** one possible.

Return _the resulting string. If there is no way to replace a character to make it not a palindrome, return an **empty string**._

A string `a` is lexicographically smaller than a string `b` (of the same length) if in the first position where `a` and `b` differ, `a` has a character strictly smaller than the corresponding character in `b`. For example, `"abcc"` is lexicographically smaller than `"abcd"` because the first position they differ is at the fourth character, and `'c'` is smaller than `'d'`.

**Example 1:**

**Input:** palindrome = "abccba"
**Output:** "aaccba"
**Explanation:** There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba".
Of all the ways, "aaccba" is the lexicographically smallest.

**Example 2:**

**Input:** palindrome = "a"
**Output:** ""
**Explanation:** There is no way to replace a single character to make "a" not a palindrome, so return an empty string.

**Constraints:**

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

# Approaches
## Brute-Force Generation and Check
This approach systematically generates every possible string that can be formed by changing a single character of the input palindrome. For each generated string, it checks if it's non-palindromic. All such valid strings are collected, and the lexicographically smallest among them is returned.
**Time:** O(N^2). The outer loop runs N times, and the inner loop runs 26 times. Inside the loops, creating a new string and checking if it's a palindrome both take O(N) time. This results in a total complexity of O(N * 26 * N) which simplifies to O(N^2). Sorting the candidates adds further overhead. · **Space:** O(N^2), where N is the length of the string. In the worst-case scenario, we might need to store O(N) candidate strings, each of length N.
**Pros:** It is a straightforward and easy-to-understand implementation.; It is guaranteed to find the correct solution because it exhaustively checks all possibilities.
**Cons:** Highly inefficient with a time complexity of O(N^2).; Requires significant space to store all candidate strings, leading to O(N^2) space complexity in the worst case.; Performs many redundant computations, as it doesn't use the properties of palindromes or the lexicographical requirement to prune the search space.
### Explanation
The brute-force method explores the entire search space of single-character modifications. It iterates through each position in the string and tries substituting every possible lowercase letter. For each substitution that results in a new string, it verifies two conditions: that the new string is not a palindrome and that it was formed by changing exactly one character. All strings that satisfy these conditions are collected. Finally, from this collection of valid outcomes, the one that comes first in lexicographical order is selected as the answer. If no such string can be formed (e.g., for a single-character input), the collection remains empty, and an empty string is returned.

```java
class Solution {
    public String breakPalindrome(String palindrome) {
        int n = palindrome.length();
        if (n <= 1) {
            return "";
        }

        java.util.List<String> candidates = new java.util.ArrayList<>();

        // Iterate through each position
        for (int i = 0; i < n; i++) {
            char originalChar = palindrome.charAt(i);
            // Try replacing with every lowercase letter
            for (char c = 'a'; c <= 'z'; c++) {
                if (c == originalChar) {
                    continue;
                }
                char[] arr = palindrome.toCharArray();
                arr[i] = c;
                String temp = new String(arr);
                if (!isPalindrome(temp)) {
                    candidates.add(temp);
                }
            }
        }

        if (candidates.isEmpty()) {
            return "";
        }

        // Find the lexicographically smallest candidate
        java.util.Collections.sort(candidates);
        return candidates.get(0);
    }

    private boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
- Initialize an empty list `candidates` to store valid non-palindromic strings.
- Get the length `n` of the input `palindrome`.
- Handle the edge case: if `n <= 1`, it's impossible to make a non-palindrome, so return an empty string `""`.
- Iterate through each character of the palindrome with an index `i` from `0` to `n-1`.
- For each position `i`, iterate through all possible lowercase characters `c` from 'a' to 'z'.
- If the replacement character `c` is the same as the original character at `palindrome[i]`, skip to the next character to avoid making an identical string.
- Create a new candidate string `temp` by replacing the character at index `i` with `c`.
- Check if `temp` is a palindrome. A helper function can be used for this, which compares characters from both ends moving inwards.
- If `temp` is not a palindrome, add it to the `candidates` list.
- After all possible single-character replacements have been generated and checked, find the lexicographically smallest string in the `candidates` list. This can be done by sorting the list and picking the first element.
- If the `candidates` list is empty, return `""`. Otherwise, return the smallest candidate found.

## Greedy Single Pass
This approach leverages the requirement for the lexicographically smallest result. To achieve this, we should aim to make the smallest possible change (i.e., to character 'a') at the earliest possible position in the string. This can be done efficiently in a single pass through the first half of the string.
**Time:** O(N). The algorithm consists of a single loop that iterates up to N/2 times. Converting the string to and from a character array also takes O(N) time. · **Space:** O(N), where N is the length of the string. This is because strings are immutable in Java, and we need a character array or `StringBuilder` of size N to perform modifications.
**Pros:** Extremely efficient with a linear time complexity of O(N).; Optimal in terms of logic, as it finds the solution in a single pass.; Uses minimal space, O(N) for the character array (or O(1) in languages with mutable strings).
**Cons:** The logic for the case where the first half is all 'a's is a specific edge case that must be handled correctly.; In languages with immutable strings like Java, it still requires O(N) space to create a mutable copy of the string.
### Explanation
The greedy strategy is based on a key insight: to make a string lexicographically smaller, we should change a character to a smaller value as early as possible. The smallest character is 'a'. Therefore, we iterate through the first half of the palindrome and replace the first character we encounter that is not 'a' with 'a'. This guarantees the smallest possible lexicographical result that is not a palindrome. We only need to check the first half because changing `s[i]` automatically breaks the symmetry with `s[n-1-i]`. We must not change the middle character of an odd-length palindrome, as it would remain a palindrome (e.g., "aba" -> "aaa"). Iterating only up to `n/2` naturally avoids this.

If the entire first half is composed of 'a's (implying the whole string is 'a's, like "aaaaa"), changing any 'a' to a different character will make the string lexicographically larger. To minimize this increase, we should make the change at the latest possible position. Thus, we change the last character to 'b'.

```java
class Solution {
    public String breakPalindrome(String palindrome) {
        int n = palindrome.length();
        if (n <= 1) {
            return "";
        }

        char[] arr = palindrome.toCharArray();

        // Iterate through the first half of the string.
        // We only need to find the first non-'a' character and change it to 'a'.
        for (int i = 0; i < n / 2; i++) {
            if (arr[i] != 'a') {
                arr[i] = 'a';
                return String.valueOf(arr);
            }
        }

        // If the loop finishes, it means the first half is all 'a's.
        // e.g., "aaaa", "aba".
        // To make the lexicographically smallest change, we change the last character to 'b'.
        arr[n - 1] = 'b';
        return String.valueOf(arr);
    }
}
```
### Algorithm
- Get the length `n` of the `palindrome`.
- Handle the base case: if `n <= 1`, return an empty string `""`.
- Convert the string to a mutable data structure, like a character array `arr`, to allow modifications.
- Iterate through the first half of the string, from index `i = 0` to `n / 2 - 1`.
- In the loop, find the first character `arr[i]` that is not 'a'.
- If such a character is found, change it to 'a'. This is the earliest possible position to make the lexicographically smallest change. Return the modified string.
- If the loop completes without finding any non-'a' character, it implies the entire first half of the string consists of 'a's (e.g., "aaaa" or "aba").
- In this special case, to make the string non-palindromic while keeping it lexicographically as small as possible, change the very last character `arr[n-1]` to 'b'.
- Return the resulting string.

# Solutions
### Java

```java
class Solution {
public
  String breakPalindrome(String palindrome) {
    int n = palindrome.length();
    if (n == 1) {
      return "";
    }
    char[] cs = palindrome.toCharArray();
    int i = 0;
    while (i < n / 2 && cs[i] == 'a') {
      ++i;
    }
    if (i == n / 2) {
      cs[n - 1] = 'b';
    } else {
      cs[i] = 'a';
    }
    return String.valueOf(cs);
  }
}

```

### CPP

```cpp
class Solution {
public:
  string breakPalindrome(string palindrome) {
    int n = palindrome.size();
    if (n == 1) {
      return "";
    }
    int i = 0;
    while (i < n / 2 && palindrome[i] == 'a') {
      ++i;
    }
    if (i == n / 2) {
      palindrome[n - 1] = 'b';
    } else {
      palindrome[i] = 'a';
    }
    return palindrome;
  }
};

```

### Python

```python
class Solution:
    def breakPalindrome(self, palindrome: str) -> str: n = len(palindrome) if n == 1: return "" s = list(palindrome) i = 0 while i < n // 2 and s[i] == "a": i += 1 if i == n // 2: s[- 1] = "b" else: s[i] = "a" return "" . join(s)

```