1169MediumStringGreedy

Spoiling a Mirror Word With One Change

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

The word mirror reads the same forwards and backwards. Change exactly one of its letters to a different lowercase letter so that the word no longer reads the same both ways.

Return the smallest word that can result, ordered as a dictionary would, or an empty string when no single change can spoil it.

Examples

Example 1

Input: mirror = "abcba"
Output: "aacba"

The first letter is already as low as it goes, so the earliest letter that can be lowered is the second, and dropping it to an a leaves the word out of step with its reverse.

Example 2

Input: mirror = "aaaa"
Output: "aaab"

Every letter is already an a, so nothing in the first half can be lowered, and raising the last letter to a b is the smallest change that spoils the mirror.

Example 3

Input: mirror = "aa"
Output: "ab"

Both letters are a, so the last one is raised to a b.

Constraints

1 <= mirror.length <= 1000
mirror holds only lowercase English letters
mirror reads the same forwards and backwards

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def break_palindrome(mirror: str) -> str:

Java

public String breakPalindrome(String mirror)

The intended approach

Time O(n) over the word.Space O(n) for the working copy.

A one-letter word can never be spoiled, since whatever it becomes still reads the same both ways, so that case returns nothing at all. Otherwise, to come out smallest the change should lower a letter as early in the word as it can. Lowering a letter to an `a` is the most it can be lowered, and doing so at the earliest letter that is not already an `a` gives the smallest word. That change must land in the first half: a letter in the second half has its mirror partner earlier, and lowering the earlier one is better; a middle letter of an odd-length word is its own partner, so changing it leaves the word reading the same both ways. If the whole first half is already `a`, nothing there can be lowered, and by the mirror the second half is all `a` too. Then the smallest spoiling change is to raise the very last letter to a `b`, since raising anything earlier would give a larger word.

Pythonentry point: break_palindrome

def break_palindrome(mirror):
    n = len(mirror)
    if n < 2:
        return ""
    body = list(mirror)
    for i in range(n // 2):
        if body[i] != "a":
            body[i] = "a"
            return "".join(body)
    body[n - 1] = "b"
    return "".join(body)

The obvious version

Try changing every letter to each of the other twenty-five, keep the results that no longer read the same both ways, and report the smallest of them. Costs the word length times the alphabet, with a reversal check each time.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_break_palindrome(mirror):
    n = len(mirror)
    best = None
    for i in range(n):
        for code in range(97, 123):
            ch = chr(code)
            if ch == mirror[i]:
                continue
            body = mirror[:i] + ch + mirror[i + 1:]
            if body != body[::-1]:
                if best is None or body < best:
                    best = body
    return best if best is not None else ""

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in