- 0
Notifications Mark All Read
- Login
- Get Prime
Minimum characters to be added at front to make string palindrome in C++
Minimum characters to be added to make string palindrome
Today we will be learning how to find the minimum characters that need to be added to make a string palindrome.
- Input : str = “ABC”
- Output : 2
We can make the above string palindrome as “CBABC” by adding ‘B’ and ‘C’ at the front.
- Start checking the string each time to see if it is a palindrome; if it isn’t, delete the last character and try again. When the string is reduced to either a palindrome or an empty string.
- The number of characters deleted from the beginning to the end will be the answer because those characters could have been inserted at the beginning of the original string in the order that makes the string a palindrome.
Minimum characters to be added to make string palindrome C++ Code
Run
#include<bits/stdc++.h> using namespace std; bool ispalindrome(string s) { int l = s.length(); int j; for(int i = 0, j = l - 1; i <= j; i++, j--) { if(s[i] != s[j]) return false; } return true; } // Driver code int main() { string s = "BABABAA"; int cnt = 0; int flag = 0; while(s.length()>0) { if(ispalindrome(s)) { flag = 1; break; } else { cnt++; // erase the last element of the string s.erase(s.begin() + s.length() - 1); } } if(flag) cout << cnt; }
2
Note
Time Complexity = O(N)
Login/Signup to comment