title: Break a Palindrome
slug: break-a-palindrome
difficulty: medium
leetcode_id: 1328
leetcode_url: https://leetcode.com/problems/break-a-palindrome/
categories:
  - strings
patterns:
  - slug: greedy
    is_optimal: true

function_signature: "def break_palindrome(palindrome: str) -> str:"

test_cases:
  visible:
    - input: { palindrome: "abccba" }
      expected: "aaccba"
    - input: { palindrome: "a" }
      expected: ""
  hidden:
    - input: { palindrome: "aa" }
      expected: "ab"
    - input: { palindrome: "aba" }
      expected: "abb"
    - input: { palindrome: "aaa" }
      expected: "aab"
    - input: { palindrome: "aaaa" }
      expected: "aaab"
    - input: { palindrome: "bab" }
      expected: "aab"
    - input: { palindrome: "abba" }
      expected: "aaba"
    - input: { palindrome: "zyzyz" }
      expected: "ayzyz"

description: |
  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'`.

constraints: |
  - `1 <= palindrome.length <= 1000`
  - `palindrome` consists of only lowercase English letters.

examples:
  - 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.'
  - 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.'

explanation:
  intuition: |
    Think of a palindrome as a mirror: the first half reflects onto the second half. To break this symmetry, we need to change exactly one character.

    The key insight is understanding what makes a string "lexicographically smallest." We want the earliest characters to be as small as possible. Since `'a'` is the smallest lowercase letter, our goal is to place an `'a'` as early as possible in the string.

    Here's the greedy strategy: scan from the left side of the string. If we find any character that is **not** `'a'`, we can change it to `'a'` to make the string lexicographically smaller. But there's a catch: in a palindrome, changing a character in the first half automatically affects the symmetry, which is exactly what we want.

    However, we must be careful with the **middle character** in odd-length palindromes. Changing only the middle character keeps the string as a palindrome (since it mirrors to itself). So we skip the middle character when looking for a character to replace.

    What if all characters in the first half are already `'a'`? Then we can't make the string smaller by changing anything in the first half. Our fallback is to change the **last character** to `'b'` — this breaks the palindrome while keeping the result as small as possible.

  approach: |
    We use a **Greedy Single-Pass Approach**:

    **Step 1: Handle the edge case**

    - If the string has length `1`, return an empty string — there's no way to replace a single character and make a single-character string non-palindromic

    &nbsp;

    **Step 2: Scan the first half of the string**

    - Iterate through indices `0` to `n // 2 - 1` (exclusive of the middle in odd-length strings)
    - For each character, check if it's **not** `'a'`
    - If we find a non-`'a'` character, replace it with `'a'` and return the result immediately
    - This guarantees the lexicographically smallest result because we change the leftmost possible character to the smallest possible value

    &nbsp;

    **Step 3: Fallback — change the last character**

    - If all characters in the first half are `'a'`, we cannot make the string smaller by changing them
    - Change the **last character** to `'b'`
    - This breaks the palindrome (since the first character remains `'a'`) while resulting in the smallest possible string

    &nbsp;

    The greedy approach works because we always prioritize changes that affect the leftmost positions first, and we always choose the smallest possible replacement character.

  common_pitfalls:
    - title: Forgetting the Single Character Edge Case
      description: |
        A string of length `1` like `"a"` is always a palindrome no matter what character it contains. Changing `"a"` to `"b"` still gives you a palindrome (any single character is a palindrome by definition).

        You must check for this case at the start and return an empty string.
      wrong_approach: "Trying to process single-character strings normally"
      correct_approach: "Return empty string immediately if length is 1"

    - title: Changing the Middle Character in Odd-Length Strings
      description: |
        In a palindrome like `"aba"`, the middle character `'b'` mirrors to itself. If you change it to `'a'`, you get `"aaa"` — still a palindrome!

        The middle character of an odd-length palindrome doesn't affect the palindrome property when changed alone. Only scan up to `n // 2` (exclusive) to avoid this trap.
      wrong_approach: "Scanning the entire first half including middle character"
      correct_approach: "Only scan indices 0 to n // 2 - 1"

    - title: Replacing 'a' with 'a'
      description: |
        If you find an `'a'` and "replace" it with `'a'`, you haven't actually changed anything, and the string remains a palindrome.

        Only replace characters that are **not** `'a'`. If a character is already `'a'`, skip it and continue scanning.
      wrong_approach: "Replacing the first character regardless of its value"
      correct_approach: "Only replace if the character is not 'a'"

    - title: Not Handling All-'a' Palindromes
      description: |
        For a string like `"aaa"` or `"aaaa"`, every character in the first half is already `'a'`. You can't make the string lexicographically smaller by changing any of them.

        The solution is to change the **last** character to `'b'`. This breaks the palindrome (first is `'a'`, last is `'b'`) and gives the smallest possible result.
      wrong_approach: "Giving up or returning empty string for all-'a' palindromes"
      correct_approach: "Change the last character to 'b' as a fallback"

  key_takeaways:
    - "**Greedy leftmost replacement**: To minimise a string lexicographically, make changes as early (leftmost) as possible with the smallest possible character"
    - "**Palindrome symmetry**: Only the first half of a palindrome needs to be checked — the second half is a mirror"
    - "**Edge cases matter**: Single-character strings and middle characters in odd-length strings require special handling"
    - "**Fallback strategy**: When the primary approach doesn't apply (all `'a'`s), have a clear secondary strategy (change last to `'b'`)"

  time_complexity: "O(n). We scan at most half the string once, where `n` is the length of the palindrome."
  space_complexity: "O(n). We create a new string to return the result (strings are immutable in Python)."

solutions:
  - approach_name: Greedy Single Pass
    is_optimal: true
    code: |
      def break_palindrome(palindrome: str) -> str:
          n = len(palindrome)

          # Single character palindromes cannot be broken
          if n == 1:
              return ""

          # Convert to list for easy character replacement
          chars = list(palindrome)

          # Scan the first half (excluding middle for odd-length)
          for i in range(n // 2):
              # Found a character that's not 'a'? Replace it with 'a'
              if chars[i] != 'a':
                  chars[i] = 'a'
                  return ''.join(chars)

          # All characters in first half are 'a'
          # Change the last character to 'b' to break palindrome
          chars[-1] = 'b'
          return ''.join(chars)
    explanation: |
      **Time Complexity:** O(n) — Single pass through at most half the string.

      **Space Complexity:** O(n) — We create a list copy of the string to modify it.

      The greedy strategy ensures we always find the lexicographically smallest result: we try to place an `'a'` as early as possible, and only fall back to changing the last character when necessary.

  - approach_name: Two-Case Analysis
    is_optimal: true
    code: |
      def break_palindrome(palindrome: str) -> str:
          n = len(palindrome)

          # Cannot break a single-character palindrome
          if n == 1:
              return ""

          # Case 1: Find first non-'a' in the first half
          half = n // 2
          for i in range(half):
              if palindrome[i] != 'a':
                  # Replace it with 'a' for smallest result
                  return palindrome[:i] + 'a' + palindrome[i+1:]

          # Case 2: All chars in first half are 'a'
          # Replace last char with 'b'
          return palindrome[:-1] + 'b'
    explanation: |
      **Time Complexity:** O(n) — Single pass through at most half the string.

      **Space Complexity:** O(n) — String concatenation creates new strings.

      This version uses string slicing instead of converting to a list. Both approaches are equivalent in complexity, but this one may be slightly more Pythonic when working with small strings.
