Bloomberg LP Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
The O(n) algorithm to find the longest palindromic sub-string is called the Manacher's Algorithm.
Here's an update to your solution.
I added two loops, first one for palindromes of odd length and second loop for palindromes of even length starting at index 0 in the string. It works irrespective of the length of string input being even or odd.
class Solution {
public:
string shortestPalindrome(string s) {
if(s.length()<=1){
return s;
}
int pos=0;
int pos1 =0;
for(int i=1;i<=s.length()/2;i++){
for(int j=1;j<=i && (i+j)<s.length();j++){
if(s[i-j]!=s[i+j]){
break;
}
if(j==i){
pos1=i*2;
}
}
}
int pos2 =0;
for(int i=0;i<=s.length()/2;i++){
for(int j=0;j<=i && (i+j+1)<s.length();j++){
if(s[i-j]!=s[i+j+1]){
break;
}
if(j==i){
pos2=i+j+1;
}
}
}
pos=max(pos1,pos2);
cout<<pos1<<","<<pos2<<":"<<pos;
if(pos+1 >= s.length()){
return s;
}
string temp=s.substr(pos+1,s.length());
reverse(temp.begin(),temp.end());
return temp+s;
}
};
class Solution {
public static String makePlaindrom(String s){
if(s.length()<=1)
return s;
StringBuilder pl=new StringBuilder(s);
int len=s.length();
for (int i = len-2; i >=0; i--) {
pl.append(s.charAt(i));
}
return pl.toString();
}
/*Driver function to check for above function*/
public static void main (String[] args) {
System.out.println("a>> "+makePlaindrom("a"));
System.out.println("ab>> "+makePlaindrom("ab"));
System.out.println("abc>> "+makePlaindrom("abc"));
System.out.println("abcde>> "+makePlaindrom("abcde"));
}
}
char[] chArr = str.toCharArray();
int mid = chArr.length/2;
boolean isPalindrome = true;
for(int i = mid; i >= 0; --i){
isPalindrome = true;
for(int j = 1; j < chArr.length-i && j < i; j++){
if(chArr[i-j] != chArr[i+j]){
isPalindrome = false;
break;
}
}
if(isPalindrome){
StringBuffer strBuff = new StringBuffer();
for(int k = chArr.length-1; k > 2*i; --k){
strBuff.append(chArr[k]);
}
strBuff.append(str);
System.out.println(strBuff.toString());
break;
}
isPalindrome = true;
}
public class test {
public static void main(String args[]) {
String value = "abc";
String palindrome = "";
String temp="";
boolean isPalindrome= checkPalindrome(value);
if (!isPalindrome) {
System.out.println("given string is not palindrome");
for (int i = value.length() - 1; i >= 0; i--) {
temp = temp + value.charAt(i);
if (checkPalindrome(temp+value)){
palindrome = temp + value;
break;
}
}
} else {
System.out.println("Given String is a palindrome");
}
System.out.println(palindrome);
}
private static boolean checkPalindrome(String value){
StringBuilder builder = new StringBuilder();
boolean isPalindrome=false;
for (int i = value.length()-1; i >= 0; i--) {
builder.append(value.charAt(i));
}
if(value.equalsIgnoreCase(builder.toString())){
isPalindrome=true;
}
return isPalindrome;
}
}
public class MakePalindrome {
public static void main(String[] args) {
System.out.println(makePalindrome("a")); // null
System.out.println(makePalindrome("ab")); // bab
System.out.println(makePalindrome("aa")); // null
System.out.println(makePalindrome("aba")); // null
System.out.println(makePalindrome("abba")); // null
System.out.println(makePalindrome("abc")); // cbabc
System.out.println(makePalindrome("abac")); // cabac
System.out.println(makePalindrome("caba")); // cabac
System.out.println(makePalindrome("abbc")); // cbbabbc
System.out.println(makePalindrome("abacdcefec")); // abacdcefecdcaba
}
private static String makePalindrome(String s) {
if (s == null || s.isEmpty() || s.length() == 1) return null;
final int length = s.length();
Outcome o1 = detectPalindrome(s, true);
Outcome o2 = detectPalindrome(new StringBuilder(s).reverse().toString(), false);
Outcome o = Outcome.pickShortest(o1, o2);
if (o == null) return null;
// otherwise
if (o.extendLeft) {
StringBuilder sb = new StringBuilder();
for (int i = length-1; i > length-1-o.extensionSize; i--) sb.append(s.charAt(i));
return sb.toString() + s;
}
else {
StringBuilder sb = new StringBuilder();
for (int i = o.extensionSize-1; i >= 0 ; i--) sb.append(s.charAt(i));
return s + sb.toString();
}
}
private static Outcome detectPalindrome(String s, boolean forward) {
LinkedList<Character> l = new LinkedList<Character>();
final int length = s.length();
boolean determinedMiddlePoint = false;
// left to right
int i = 0;
for (; i < length; i++) {
char c = s.charAt(i);
if (!determinedMiddlePoint) {
if (l.size() == 0) {
l.add(0, c);
continue;
}
else if (l.size() == 1) {
if (c == l.get(0)) {
determinedMiddlePoint = true;
l.remove();
continue;
}
else {
l.add(0, c);
continue;
}
}
else if (l.size() >= 2) {
if (c == l.get(0) || c == l.get(1)) {
determinedMiddlePoint = true;
if (c == l.get(1)) l.remove();
l.remove();
continue;
}
else {
l.add(0, c);
continue;
}
}
}
else {
if (!l.isEmpty()) {
if (c == l.get(0)) {
l.remove();
continue;
}
// otherwise
return new Outcome(true, length-1); // not feasible, just skip first char
}
else {
break; // feasible, patch left
}
}
}
if (!determinedMiddlePoint) return new Outcome(true, length-1);
// otherwise
if (i == length) {
if (l.isEmpty()) return null;
// otherwise
return new Outcome(forward?false:true, l.size());
}
// otherwise
if (i < length) {
if (l.isEmpty()) return new Outcome(forward?true:false, length-i);
// otherwise
throw new IllegalStateException(i + " " + l);
}
// otherwise
throw new IllegalStateException(i + " " + l);
}
private static class Outcome {
private final boolean extendLeft;
private final int extensionSize;
private Outcome(boolean extendLeft, int extensionSize) {
this.extendLeft = extendLeft;
this.extensionSize = extensionSize;
}
private static Outcome pickShortest(Outcome o1, Outcome o2) {
if (o1 == null) return o2;
if (o2 == null) return o1;
return (o1.extensionSize < o2.extensionSize)? o1: o2;
}
}
}
#include <iostream>
#include <string>
#include <sstream>
bool isPalindrome( std::string::const_iterator begin, std::string::const_iterator end )
{
bool result = true;
-- end;
while ( begin < end )
{
if ( * begin ++ != * end -- )
{
result = false;
break;
}
}
return result;
}
std::string asPalindrome( const std::string & input )
{
using namespace std;
ostringstream extra;
string::const_iterator begin = input.begin( );
string::const_iterator end = input.end( );
while ( ! isPalindrome( begin, end ) )
{
-- end;
extra << * end;
}
return extra.str( ) + input;
}
int main( )
{
using namespace std;
cout << "a" << " -> " << asPalindrome( "a" ) << ", expected a" << endl;
cout << "ab" << " -> " << asPalindrome( "ab" ) << ", expected bab" << endl;
cout << "abc" << " -> " << asPalindrome( "abc" ) << ", expected cbabc" << endl;
cout << "bazabc" << " -> " << asPalindrome( "bazabc" ) << ", expected cbazabc" << endl;
cout << "cbazabc" << " -> " << asPalindrome( "cbazabc" ) << ", expected cbazabc" << endl;
}
#include <iostream>
void reverseString(std::string& str)
{
size_t len = str.size() / 2;
size_t rv = str.size() - 1;
for (size_t i = 0; i < len; ++i, --rv)
{
char tmp = str[rv];
str[rv] = str[i];
str[i] = tmp;
}
}
std::string makePalindrome(const std::string& src)
{
if (src.size() <= 1)
{
return src;
}
std::string result = src.substr(1, (src.size() - 1));
reverseString(result);
return result.append(src);
}
int main()
{
std::string src1 = "abc";
std::string src2 = "ab";
std::string src3 = "a";
std::cout << makePalindrome(src1).c_str() << std::endl;
std::cout << makePalindrome(src2).c_str() << std::endl;
std::cout << makePalindrome(src3).c_str() << std::endl;
return 0;
}
#include <iostream>
void reverseString(std::string& str)
{
size_t len = str.size() / 2;
size_t rv = str.size() - 1;
for (size_t i = 0; i < len; ++i, --rv)
{
char tmp = str[rv];
str[rv] = str[i];
str[i] = tmp;
}
}
std::string makePalindrome(const std::string& src)
{
if (src.size() <= 1)
{
return src;
}
std::string result = src.substr(1, (src.size() - 1));
reverseString(result);
return result.append(src);
}
int main()
{
std::string src1 = "abc";
std::string src2 = "ab";
std::string src3 = "a";
std::cout << makePalindrome(src1).c_str() << std::endl;
std::cout << makePalindrome(src2).c_str() << std::endl;
std::cout << makePalindrome(src3).c_str() << std::endl;
return 0;
}
class Main {
//Given a string, add some characters to the from of it so that it becomes a palindrome. E.g.1) If input is "abc" then "bcabc" should be returned. 2) input -> "ab" output -> "bab" 3) input -> "a" output -> "a"
public static void main(String[] args) {
String output = makePalindrome("abc");
System.out.println(output);
}
private static String makePalindrome(String input){
if(input.length() <= 1){
return input;
}
StringBuilder sb = new StringBuilder();
for(int index = input.length() - 1; index >= input.length() / 2; index--){
sb.append(input.charAt(index));
}
sb.append(input);
return sb.toString();
}
}
- Chris December 14, 2016/* Assumptions: - He means add characters to the front of the given input to form a palindrome. - Instead of "bcabc" he meant "cbabc" because "bcabc" is not a palindrome - I assume, he as well means inserting minimum characters, because it would otherwise just being addinig n - 1 characters assuming the character at position 0 of input is the middle character, which would satisfy all the samples and description. - Because of the many assumptions, I add a simplification to only consider "odd-size" palindromes (which have mirror character, -> do not mirror in-between characters) Solution O(n^2) - Adding minimal amount to the front, means finding the longest palindrome that mirrors the front part of the input completely. e.g. "abzbahik" would be "abzba" "hik" needs to be reversed and inserted at the front - Then "insert" the missing characters to the front - There is a O(n) solution for finding the palindrome you may look it up, I didn't include it here... */ #include <iostream> #include <string> #include <algorithm> using namespace std; string extendPalindrome(const string& input) { if(input.length() <= 1) return input; // find mirror point (as mentioned only consider odd palindrome for simplicity) int pos = 0; for(int i = 1; i <= input.length() / 2; i++) // i: mirror point { for(int j = 1; i + j < input.length() && i - j >= 0; j++) { if(input[i + j] != input[i - j]) break; if(j == i) pos = i; } } // insert at beginning int rem = input.length() - (pos + pos + 1); if(rem == input.length()) return input; string result = input.substr(pos + pos + 1, rem); reverse(result.begin(), result.end()); result.append(input); return result; } int main() { cout << "a: " << extendPalindrome("a") << endl; cout << "ab: " << extendPalindrome("ab") << endl; cout << "abc: " << extendPalindrome("abc") << endl; cout << "bazabc: " << extendPalindrome("bazabc") << endl; cout << "cbazabc: " << extendPalindrome("cbazabc") << endl; } /* output a: a ab: bab abc: cbabc bazabc: cbazabc cbazabc: cbazabc */