Array ( [0] => [1] => questions [2] => Strings [3] => Min-No-of-elements ) Strings | Min No of elements | THE INQUISITIVE






Min No of elements

LEVEL:Beginner

Description

Given a string K. You have to remove the minimum number of characters such that it becomes a palindrome.

Input Format

First line contains the string K

Output Format

Print the minimum number.


Example 1:

Input
abaa
Output
1
Example 2:

Input
abcdcaba
Output
1
Example 3:

Input
seeks
Output
1

oops

Login to see Discussion




Approach

step-i) copy the reverse of the string in the stringbuilder
step-ii)create a 2D array dp of size n*n
step-iii)run loop from i=0 to i<=len and initialize dp[0][i]=i and dp[i][0] = i
step-iv)initialize i =1
step-v)initialize j = 1
step-vi) if for given string character at i-1 is equal to character at j-1 of reversed string dp[i][j] = dp[i-1][j-1]
step-vii)else dp[i][j]= 1+ minimum of (dp[i-1][j] and dp[i][j-1])
step-ix)repeat steps vi to viii till j is less than or equal to length of string
step-x)increment i by one value
step-xi) repeat steps v to x till i is less than or equal to length of string
step-xii) initialize answer to max value possible
step-xiii) initialize i to len and j to 0
step-xiv) assign min of answer and dp[i][j] to answer
step-xv) if i is less than len assign min of answer and dp[i+1][j] to answer
step-xvi) if i is greater than 0 assign min of answer and dp[i-1][j] to answer
step-xvii)increment j value by one and decrement i value by one
step-xviii) repeat steps xiv to xvii till i is greater than 0
step-xix)return answer

Time Complexity: O(n^2) where n is length of the string
Space Complexity: O(n^2)


Note :

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

oops

Login to see Solution






     Recommended Questions      

Topic: Strings

Beginner

1. Timing Format2. Date Format3. Palindrome 4. Anagrams5. Balanced Parenthesis6. Equal Strings7. Smallest Window8. Reverse of String9. Distinct Palindromes10. Remove adjacent duplicates11. Run length encoding12. Non repeating Character13. Array of strings14. Find Excel Column15. Transform one string to another16. Move Robot in circular17. Zig Zag concatenation. 18. Min No of elements19. Combination of strings used to dial a number20. Ancient String