---
# System prepended metadata

title: 1312. Minimum Insertion Steps to Make a String Palindrome
tags: [leetcode]

---

# 1312. Minimum Insertion Steps to Make a String Palindrome
###### tags: `leetcode`
## Description
Given a string s. In one step you can insert any character at any index of the string.

Return the minimum number of steps to make s palindrome.

A Palindrome String is one that reads the same backward as well as forward.

- Example 1:

>Input: s = "zzazz"
Output: 0
>>Explanation: The string "zzazz" is already palindrome we do not need any insertions.

- Example 2:

>Input: s = "mbadm"
Output: 2
>>Explanation: String can be "mbdadbm" or "mdbabdm".

- Example 3:

>Input: s = "leetcode"
Output: 5
>>Explanation: Inserting 5 characters the string becomes "leetcodocteel".

- Constraints:

>$1 \leq s.length \leq 500$
s consists of lowercase English letters.

## Solution
- The problem is a dynamic problem. With each of the vector node as the number needed to add for the substring
- To calculate the value, the direction to count should be a starting index in a closest end and move it gradually backward to the starting point
```cpp=
for (int i = n - 2; i >= 0; i--) {
```
- In the iteration, move the end index foreward in order to extend the substring length.
- The calculation should start from length equal to `2` because for length = 1, all of them are palindrome
    - The `prev` starts with `0` because the starting previous value is one character and the number to add is 0
- By extending the length, it means the original substring plus one character in the front because the starting point is moving backward
- Thus, if the front is equal to the back, the dp value is the same
```cpp=
if (s[i] == s[j]) dp[j] = prev;
```
- If the two are different, two possibilities can construct the substring
    - Adding the front character with the rest of the substring
    - Add the back character with the rest of the substring
    - Both possibilities need to add `1` in the back or front
```cpp=
else dp[j] = min(dp[j], dp[j - 1]) + 1;
```
- The previous value is stored as the last time for the substring that is one fore character less from the next iteration
```cpp=
int temp = dp[j];
prev = temp;
```
- Fianlly return back the final value
```cpp=
return dp[n - 1];
```