top of page

Looking to master object-oriented and system design for tech interviews or career growth?

• Improve your system design and machine coding skills.

• Study with our helpful resources.

**We're in beta mode and would love to hear your feedback.

Search

Minimum Characters required to make a String Palindromic InterviewBit Solution

Problem Statement:

Given a string A. The only operation allowed is to insert characters at the beginning of the string.

Find how many minimum characters are needed to be inserted to make the string a palindrome string.

Input Format

The only argument given is string A.

Output Format

Return the minimum characters that are needed to be inserted to make the string a palindrome string.

For Example

```Input 1:
A = "ABC"
Output 1:
2
Explanation 1:
Insert 'B' at beginning, string becomes: "BABC".
Insert 'C' at beginning, string becomes: "CBABC".

Input 2:
A = "AACECAAAA"
Output 2:
2
Explanation 2:
Insert 'A' at beginning, string becomes: "AAACECAAAA".
Insert 'A' at beginning, string becomes: "AAAACECAAAA".```

Approach:

Each index of the LPS array contains the longest prefix which is also a suffix. Now take the string and reverse of a string and combine them with a sentinel character in between them and compute the LPS array of this combined string. Now take the last value of the LPS array and subtract it with the length of the original string, This will give us the minimum number of insertions required at the beginning of the string.

Time & Space Complexity:

`Time Complexity: O(N)`

Code in C++

bottom of page