Palindrome by Adding Letters

Hard

You are given a word word of lowercase English letters. In one move you can insert any letter anywhere in the word, including the very start or end. Return the smallest number of moves after which the word reads the same forwards and backwards.

Example 1

word="kayak" → 0

The word already reads the same both ways.

Example 2

word="tab" → 2

Two letters are needed, for example to get "batab".

Example 3

word="abca" → 1

One letter is enough: "abcba" or "acbca".

Constraints

1 ≤ len(word) ≤ 500
word consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Does the Text Fit the Pattern Hard Shuffle by Cutting and Swapping Hard Ways to Cross Out Hard

Input

word="kayak"

Expected

Run checks the first 3 tests in your browser. Submit checks all 126 tests on the server, hidden ones included.