LeetCode 1328: Break a Palindrome (TypeScript)

In this post I'll share my code for solving LeetCode question 1328 - Break a Palindrome in TypeScript.

Result: Accepted

• Runtime: 66ms (beats 22%)
• Memory: 43.2MB (beats 44.44%)

This answer runs in about O(n) with constant memory. Based on the comparisons with other answers, my guess is there may be a more optimal solution but I think O(n) is reasonably good in most cases so I'm fine with this.

const swapCharacterInString = (
    originalString : string,
    indexToSwap : number,
    characterToSwap : string
) : string => {
    return originalString.substring(0, indexToSwap)
        + characterToSwap
        + originalString.substring(indexToSwap + 1)
}

function breakPalindrome(palindrome: string): string {
    if(palindrome.length <= 1) {
        return ""
    }

    const middleIndex = (palindrome.length % 2 === 1)
        ? Math.floor(palindrome.length / 2)
        : null
    for(let i = 0; i < palindrome.length; i++) {
        if(middleIndex !== null 
            && i === middleIndex) {
            continue
        }

        const letter = palindrome[i]
        if(letter !== "a") {
            // hamytodo - return with a swapped
            return swapCharacterInString(
                palindrome,
                i,
                "a"
            )
        }
    }

    // hamytodo - return with last letter == b
    return swapCharacterInString(
        palindrome,
        palindrome.length - 1,
        "b"
    )
};

/*
* Given: A string that is a palindrome
    * Lowercase
* Goal: Break the palindrome -> lexicographically smallest possible
    * Constraint: Only change one letter
    * If cannot replace character -> empty string

Best: O(n) -> potentially faster?

SubProblems:
* A: Finding character to change to make it sortably smallest
    * 1: Greedy find O(n), 1
        * Normal Case: 
            * Search left to right for first element != "a" && != middleElemetn -> reduce to "a"
            * Skip if middle element
        * Edge case: If nothing found:
            * Right to left -> bump last thing to "b"
* B: Identify if cannot replace anything to make it not a palindrome 
    * 1: Only happens if 1 character??? O(1)

Options:
* A: Check if changeable, search for smallest thing to change - O(n), 1
    * B.1 - Check if only one character -> return "" - O(1)
    * A.1 - Greedy find to right, swap to left - O(n), 1
*/