Bloomberg LP Interview Question
Software Engineer / DevelopersCountry: 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