Break a Palindrome Algorithm
TikTokProduct Manager · Online Assessment
Last updated
Practice the greedy algorithm for breaking a palindrome into the lexicographically smallest non-palindrome by one character replacement. The solution explains scanning the left half, skipping the middle character, changing the first non-a to a, handling all-a cases, proving correctness, and analyzing complexity.
Question
Given a palindromic string of lowercase English letters (1 ≤ length ≤ 1, 000), replace exactly one character so that the result is no longer a palindrome and is the lexicographically smallest string possible. Return the new string, or an empty string if it cannot be done.
Describe your algorithm, key edge cases (e.g., single-character input), and analyze time and space complexity.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.