## Google Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
7
of 7 vote

``````def get_longest_palindrome(my_string) :

#store the number of times each character occurs in the input my_string
counter = dict.fromkeys(list(my_string), 0)
for l in list(my_string) :
counter[l] = counter[l] + 1

#we will construct the largest palindrome as half_word + center + reversed(half_word)
half_word = ''
center = ''

for letter in counter :
#store in a list the number of times letter occurs divided by two and if it occurs odd or even times
quot_mod = divmod(counter[letter],2)
#create a string repeating letter the number of times it occurs in input my_string divided by 2
#add the string constructed above to the half_word

#if letter occurs an odd number of times use it as a center letter
if quot_mod[1] == 1:
center = letter
return half_word + center + half_word[::-1]

#examples
print(get_longest_palindrome('abbacch'))
print(get_longest_palindrome('aabbsddfgh'))

Comment hidden because of low score. Click to expand.
4
of 4 vote

we can do it simply greedily: get the letter counter, and for even number of occurrence, keep them, odd number of occurrence, keep the largest one and take the others by dropping one letter.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````public class Solution {

public static void main(String [] args) {

System.out.println(getPalindrome("aha"));
System.out.println(getPalindrome("ttaatta"));
System.out.println(getPalindrome("abc"));
System.out.println(getPalindrome("gggaaa"));
}

public static String getPalindrome(String str) {

int [] chars = new int[27];

str.chars().forEach(c -> chars[c-'a']++);

StringBuilder buf = new StringBuilder();

for (int i = 0; i < 27; i++) {
if (chars[i] >= 2) {
int count = chars[i] / 2;
chars[i] -= count*2;
while (count > 0) {
buf.append((char) (i+'a'));
count--;
}
}
}

String end = buf.toString();

buf.reverse();

for (int i = 0; i < 27; i++) {
if (chars[i] >= 1) {
buf.append((char) (i+'a'));
break;
}
}

return buf.toString() + end;
}

}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

//Time Complexity: O(N) where N is the size of the input string.Space is O(N).

``````public class Solution
{
public static String constructPalindrome(String str)
{
if(str==null||str.length()==0)
{
return str;
}
if(str.length()==1)
{
return str;
}
if(isPalindrome(str))
{
return str;
}
return getLongestPalindrome(str);
}

private static boolean isPalindrome(String str) {
int i=0;
int j=str.length()-1;
while(i<j)
{
if(str.charAt(i)!=str.charAt(j))
{
return false;
}else
{
i++;
j--;
}
}
return true;
}

private static String getLongestPalindrome(String str) {
int[] c=new int[26];
for(int i=0;i<str.length();i++)
{
c[(int)str.charAt(i)-'a']++;
}

int oddCounts=0;
for(int i=0;i<c.length;i++)
{
if(c[i]%2!=0)
{
oddCounts++;

}
}
int i=0;
while(oddCounts>1 && i<c.length)
{
if(c[i]%2!=0)
{
c[i]--;
oddCounts--;
}
i++;
}
return buildString(c,str);
}

private static String buildString(int[] c,String s) {
StringBuilder sb=new StringBuilder(s);
int oddIdx=-1;
int a=0;
int b=sb.length()-1;
for(int i=0;i<c.length;i++)
{
if(c[i]%2!=0)
{
oddIdx=i;

}else
{
while(c[i]>0)
{
char v=(char)(i+'a');
sb.setCharAt(a, v);
sb.setCharAt(b, v);
a++;
b--;
c[i]-=2;
}
}
}
if(oddIdx!=-1)
{
while(c[oddIdx]>0)
{
char x=(char)(oddIdx+'a');
sb.setCharAt(a,x );
sb.setCharAt(b, x);
a++;
b--;
c[oddIdx]-=2;
}
}
return sb.toString();
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <string>
#include <iostream>
#include <unordered_map>
using namespace std;

unordered_map<string, int>  buildFreq(const string &s){
unordered_map<string, int> freq;
for(char ch:s){
string c(1,ch);
if (freq.count(c)==0){
freq[c] = 1;
}else{
freq[c] += 1;
}
}
return freq;
}

string longestPal(const string &s){
unordered_map<string, int> freq = buildFreq(s);
string L, M, R, c;
M="";
int count;

for(auto it=freq.begin(); it!=freq.end(); it++){
c = it->first;
count = it->second;

if(count>2){
while(count>1){
L=L+c;    // forward string
R=c+R;    // reverse of L
count=count-2;
}
}
// either count is 1 to begin with or the left over is now 1
if (count==1){
M=c;
}
}

return L+M+R;
}

void longPalTest(){
string s = "gggaaa";
cout << "Input s: " << s << endl;
cout << "Longest Palindrome: " << longestPal(s) << endl;
}

int main(){
longPalTest();
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Swift.

``````//: Playground - noun: a place where people can play

import UIKit

var str = "Hello, playground"

// Keys are letters, values are letter occurences.
func createLetterCountDictionary(word:String!) -> [String: Int] {
var result = [String: Int]()
var characters = word.characters
while (characters.count > 0) {
let character = String(characters.first!)
if (result[character] == nil) {
result[character] = 1

} else {
result[character] = result[character]! + 1

}
characters = characters.dropFirst()

}
return result

}

func makePalindrome(word:String) -> String! {
// Get a dictionary of letters/occurences and an array of sorted keys by value.
let letterCountDictionary = createLetterCountDictionary(word)
let sortedKeys = Array(letterCountDictionary.keys).sort({letterCountDictionary[\$0] < letterCountDictionary[\$1]})

var leftString:String! = ""
var centerString:String! = ""
var rightString:String! = ""
var centerFound = false

for letter in sortedKeys {
if var letterCount = letterCountDictionary[letter] {
if (letterCount % 2 == 1 && centerFound == false) {
// We have the largest odd value. Place it in the middle.
while (letterCount > 0) {
centerString = centerString.stringByAppendingString(letter)
letterCount -= 1

}
centerFound = true

} else {
if (letterCount % 2 == 1) {
// Not the largest odd value, make it even.
letterCount -= 1

}

// We have an even amount. Split it amongst left and right.
letterCount = letterCount / 2
while (letterCount > 0) {
letterCount -= 1

}

}

}

}
return leftString + centerString + rightString

}

makePalindrome("aha") // "aha"
makePalindrome("ttaatta") // "ttaaatt"
makePalindrome("abc") // "b"
makePalindrome("gggaaa") // "gaaag"``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Swift

``````//: Playground - noun: a place where people can play

import UIKit

var str = "Hello, playground"

// Keys are letters, values are letter occurences.
func createLetterCountDictionary(word:String!) -> [String: Int] {
var result = [String: Int]()
var characters = word.characters
while (characters.count > 0) {
let character = String(characters.first!)
if (result[character] == nil) {
result[character] = 1

} else {
result[character] = result[character]! + 1

}
characters = characters.dropFirst()

}
return result

}

func makePalindrome(word:String) -> String! {
// Get a dictionary of letters/occurences and an array of sorted keys by value.
let letterCountDictionary = createLetterCountDictionary(word)
let sortedKeys = Array(letterCountDictionary.keys).sort({letterCountDictionary[\$0] < letterCountDictionary[\$1]})

var leftString:String! = ""
var centerString:String! = ""
var rightString:String! = ""
var centerFound = false

for letter in sortedKeys {
if var letterCount = letterCountDictionary[letter] {
if (letterCount % 2 == 1 && centerFound == false) {
// We have the largest odd value. Place it in the middle.
while (letterCount > 0) {
centerString = centerString.stringByAppendingString(letter)
letterCount -= 1

}
centerFound = true

} else {
if (letterCount % 2 == 1) {
// Not the largest odd value, make it even.
letterCount -= 1

}

// We have an even amount. Split it amongst left and right.
letterCount = letterCount / 2
while (letterCount > 0) {
letterCount -= 1

}

}

}

}
return leftString + centerString + rightString

}

makePalindrome("aha") // "aha"
makePalindrome("ttaatta") // "ttaaatt"
makePalindrome("abc") // "b"
makePalindrome("gggaaa") // "gaaag"``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Short and simple:

``````def maxPalindrome(string):
count = collections.Counter(string)
odds = {key: val for (key, val) in count.items() if val % 2 != 0}
evens = {key: val for (key, val) in count.items() if val % 2 == 0}
maxodds = "" if not odds else max(odds)
result = ""
for char in evens:
result += char * (count[char] // 2)
for char in odds:
if char != maxodds:
result += char * ((count[char] - 1) // 2)
return result + (maxodds * odds.get(maxodds, 0)) + result[::-1]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````function LongestPalindrome(str)
{
var oHash = new Object();

for(var i=0; i<str.length; i++)
oHash[str[i]] = typeof(oHash[str[i]]) == "undefined" ? 1 : oHash[str[i]]+1;

var cCenter;

// Option I.
var sLP = "";

for(var char in oHash)
{
if(oHash[char] % 2 == 1 && !cCenter)
cCenter = char;
if(oHash[char] > 1)
sLP += Array((oHash[char] >> 1) + 1).join(char);
}

if(cCenter)
sLP += cCenter;

for(var i=sLP.length-2; i>=0; i--)
sLP += sLP[i];

return sLP;

/*
// Option II.
var oLP = new Array();

for(var char in oHash)
{
if(oHash[char] % 2 == 1 && !cCenter)
cCenter = char;
if(oHash[char] > 1)
{
for(var j=0; j<(oHash[char] >> 1); j++)
{
oLP.push(char);
oLP.unshift(char);
}
} // if
} // for

if(cCenter)
oLP.splice(oLP.length ? oLP.length >> 1 : 0, 0, cCenter)

return oLP.join("");
*/

} // LongestPalindrome``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>

template <typename Container>
Container Reversed(Container c) {
std::reverse(c.begin(), c.end());
return c;
}

template <typename Container>
Container FilledWith(const typename Container::value_type& item, int n) {
Container c(n, item);
return c;
}

std::string LongestPalindrome(const std::string& s) {
std::unordered_map<char, int> character_occurances;
for (char c : s) {
++character_occurances[c];
}

std::string evens;
std::string max_odds;

for (auto character_frequency : character_occurances) {
std::size_t tossed = 0;
while (character_frequency.second % 2 == 1) {
++tossed;
--character_frequency.second;
}

evens += FilledWith<std::string>(character_frequency.first,
character_frequency.second / 2);
if (tossed > max_odds.size()) {
max_odds = FilledWith<std::string>(character_frequency.first, tossed);
}
}

return evens + max_odds + Reversed(evens);
}

int main() {
std::cout << LongestPalindrome("aha") << std::endl;
std::cout << LongestPalindrome("ttaatta") << std::endl;
std::cout << LongestPalindrome("gggaaa") << std::endl;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>

template <typename Container>
Container Reversed(Container c) {
std::reverse(c.begin(), c.end());
return c;
}

template <typename Container>
Container FilledWith(const typename Container::value_type& item, int n) {
Container c(n, item);
return c;
}

std::string LongestPalindrome(const std::string& s) {
std::unordered_map<char, int> character_occurances;
for (char c : s) {
++character_occurances[c];
}

std::string evens;
std::string max_odds;

for (auto character_frequency : character_occurances) {
std::size_t tossed = 0;
while (character_frequency.second % 2 == 1) {
++tossed;
--character_frequency.second;
}

evens += FilledWith<std::string>(character_frequency.first,
character_frequency.second / 2);
if (tossed > max_odds.size()) {
max_odds = FilledWith<std::string>(character_frequency.first, tossed);
}
}

return evens + max_odds + Reversed(evens);
}

int main() {
std::cout << LongestPalindrome("aha") << std::endl;
std::cout << LongestPalindrome("ttaatta") << std::endl;
std::cout << LongestPalindrome("gggaaa") << std::endl;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Time complexity is O(n):

``````std::string FindLongestPalindrome(const std::string &str) {
// 1. build charCountMap with str
typedef std::unordered_map < char, int > CharCountMap;
CharCountMap charCountMap;
for (int i = 0; i < str.size(); ++i) {
char c = str[i];
CharCountMap::iterator it = charCountMap.find(c);
if (it == charCountMap.end()) {
charCountMap.insert(CharCountMap::value_type(c, 1));
} else {
it->second++;
}
}

// 2. build left half part of palindrome and find if there is a middleChar
// 0 means no middleChar
char middleChar = 0;
std::string result;
for (CharCountMap::iterator i = charCountMap.begin(); i != charCountMap.end(); ++i) {
char c = i->first;
int count = i->second;
if (count >= 2) {
for (int j = 0; j < count / 2; ++j) {
result += c;
}
}
if (middleChar == 0 && count % 2 == 1) {
middleChar = c;
}
}

// 3. append middleChar if needed
int size = result.size();
if (middleChar != 0) {
result += middleChar;
}

// 4. append right half part with left half part
for (int i = size - 1; i >= 0; --i) {
result += result[i];
}

return result;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Main {

public static void main(String[] args) {
//String s = "ttaatta"; //attatta
//String s = "ttaatt"; //atttta
String s = "ttaata"; //attta
printLongestPalindrome(s);
}

public static void printLongestPalindrome(String s){
HashMap<Character,Integer> map = new HashMap<>();
for(Character c:s.toCharArray()){
if(map.containsKey(c)){
map.put(c, map.get(c)+1);
}else{
map.put(c, 1);
}
}

int oddMaxCount = 0;
StringBuffer result1 = new StringBuffer("");
StringBuffer result2 = new StringBuffer("");
for(Character key:map.keySet()){
if(map.get(key)%2!=0){
oddMaxCount = Math.max(oddMaxCount, map.get(key));
}
for(int i=0;i<map.get(key)/2;i++){
result1.append(key);
}
}
char middle='q';
boolean middleExists = false;
for(Character key:map.keySet()){
if(map.get(key)%2!=0 && map.get(key)==oddMaxCount){
middle = key;
middleExists = true;
}
for(int i=0;i<map.get(key)/2;i++){
result2.append(key);
}
}

if(middleExists)System.out.println(result1+Character.toString(middle)+result2.reverse());
else System.out.println(result1+""+result2.reverse());
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def get_polindrom(s):
d = collections.defaultdict(int)
for char in s:
d[char] += 1
result = []
for k, v in d.items():
if v % 2 != 0:
result = result[:(len(result)/2)] + [k] * v + result[(len(result)/2):]
else:
result += [k] * (v // 2)
result = [k] * (v // 2) + result
return "".join(result)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

var LP = LP || {};

LP.find = function(str) {
var arr = str.split("");
var l = arr.length;

if (l === 0) {
return false;
}

if (l === 1) {
return arr;
}

var dict = [];
var u = [];

for (var i = 0; i < l; i++) {
if (!dict[arr[i]]) {
dict[arr[i]] = 1;
u.push(arr[i]);
} else {
dict[arr[i]] = dict[arr[i]] + 1;
}
}

var s = "";
var singles = [];
var tmp = [];
while (u.length) {
var val = u.pop()
var max = dict[val];
if (max === 1) {
singles.push(val);
} else {
while (max % 2 !== 0) {
max--;
}
for (var k = 0; k < max; k = k + 2) {
tmp.unshift(val);
tmp.push(val);
}
}
}
s = tmp.join("");
if (singles.length > 0) {
var a = s.split("");

var a1 = a.slice(0, Math.floor(a.length / 2));
var a2 = a.slice(Math.floor(a.length / 2));

a1.push(singles[0]);
return a1.concat(a2).join("");
} else {
return s;
}
};

LP.find("abbacch");

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````var LP = LP || {};

LP.find = function(str) {
var arr = str.split("");
var l = arr.length;

if (l === 0) {
return false;
}

if (l === 1) {
return arr;
}

var dict = [];
var u = [];

for (var i = 0; i < l; i++) {
if (!dict[arr[i]]) {
dict[arr[i]] = 1;
u.push(arr[i]);
} else {
dict[arr[i]] = dict[arr[i]] + 1;
}
}

var s = "";
var singles = [];
var tmp = [];
while (u.length) {
var val = u.pop()
var max = dict[val];
if (max === 1) {
singles.push(val);
} else {
while (max % 2 !== 0) {
max--;
}
for (var k = 0; k < max; k = k + 2) {
tmp.unshift(val);
tmp.push(val);
}
}
}
s = tmp.join("");
if (singles.length > 0) {
var a = s.split("");

var a1 = a.slice(0, Math.floor(a.length / 2));
var a2 = a.slice(Math.floor(a.length / 2));

a1.push(singles[0]);
return a1.concat(a2).join("");
} else {
return s;
}
};

LP.find("abbacch");``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````from collections import defaultdict
def findLongestPalin(string):
char_dict = defaultdict(int)
for char in string:
char_dict[char] += 1
begin = ""
end = ""
mid = ""
for char in char_dict:
if char_dict[char] % 2 == 0:
begin += char * int(char_dict[char] / 2)
end += char * int(char_dict[char] / 2)
else:
begin += char * int(char_dict[char] / 2)
end += char * int(char_dict[char] / 2)
mid += char
if len(mid) > 0:
palin = begin + mid[0] + end[::-1]
else:
palin = begin + end[::-1]
return palin``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*
1. Count character occurence in input per character with a hash table
2. Construct palindrome by taking two characters out and placing them at the start and end
3. If at least one character has odd occurence, place one of it in the middle
*/

#include <string>
#include <iostream>
#include <unordered_map>

using namespace std;

string ConstructPalindrome(const string& input)
{
int size = 0; // size of the resulting palindrome
unordered_map<char, int> cm; // character count map

// count each character, if a character occures an even amount of time,
// increase the palindrome size by that size (2 each time)
for (char c : input)
{
unordered_map<char, int>::iterator it;
if ((it = cm.find(c)) != cm.end())
{
it->second++;
if (it->second % 2 == 0) size += 2;
}
else
{
cm[c] = static_cast<int>(1);
}
}

// fix size for the case there is at least one character with an odd count
// and reserve space for result
if (size < input.size()) size++;
string result(size, ' ');

// construct result
int i = 0;
int j = size - 1;
for (auto p : cm)
{
while (p.second > 1)
{
result[i++] = p.first;
result[j--] = p.first;
p.second -= 2;
}
if (p.second == 1) result[size / 2] = p.first;
}
return result;
}

int main()
{
cout << "aha: '" << ConstructPalindrome("aha") << "'" << endl;
cout << "ttaatta: '" << ConstructPalindrome("ttaatta") << "'" << endl;
cout << "abc: '" << ConstructPalindrome("abc") << "'" << endl;
cout << "gggaaa: '" << ConstructPalindrome("gggaaa") << "'" << endl;

getchar();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def longestPalindrome(s):
ss, dd = set(), []
for c in s:
if ss and c in ss:
dd.append(c)
else:

return "".join(dd) + (list(ss)[0] if ss else "") + "".join(dd[::-1])``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def longestPalindrome(s):
ss, dd = set(), []
for c in s:
if ss and c in ss:
dd.append(c)
else:

return "".join(dd) + (list(ss)[0] if ss else "") + "".join(dd[::-1])``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

/**
*/
public class LongestPalindrome {

static String longestPalin(String s) {
Map<Character, Integer> charCount = new HashMap<Character, Integer>();
for (char c : s.toCharArray()) {
if (charCount.containsKey(c)) {
charCount.put(c, charCount.get(c) + 1);
} else {
charCount.put(c, 1);
}
}
Set<Map.Entry<Character, Integer>> entries = charCount.entrySet();
Map.Entry<Character, Integer> maxOddEntry = getMaxOddEntry(entries);
Stack<Map.Entry<Character, Integer>> stack = new Stack<Map.Entry<Character, Integer>>();
StringBuilder result = new StringBuilder();
for (Map.Entry<Character, Integer> entry : entries) {
Integer value = entry.getValue();
Character character = entry.getKey();
if (maxOddEntry != null && character == maxOddEntry.getKey()) {
continue;
}
append(result, character, value / 2);
stack.push(entry);
}
if (maxOddEntry != null) {
append(result, maxOddEntry.getKey(), maxOddEntry.getValue());
}
while (!stack.isEmpty()) {
Map.Entry<Character, Integer> entry = stack.pop();
append(result, entry.getKey(), entry.getValue() / 2);
}
return result.toString();
}

private static void append(StringBuilder result, Character key, int n) {
for (int i = 0; i < n; i ++) {
result.append(key);
}
}

private static Map.Entry<Character, Integer> getMaxOddEntry(Set<Map.Entry<Character, Integer>> entries) {
int maxOddCount = 0;
Map.Entry<Character, Integer> result = null;
for (Map.Entry<Character, Integer> entry : entries) {
Integer value = entry.getValue();
if (value % 2 == 1 && value > maxOddCount) {
maxOddCount = value;
result = entry;
}
}
return result;
}

public static void main(String[] args) {
System.out.println(longestPalin("aha"));
System.out.println(longestPalin("ttaatta"));
System.out.println(longestPalin("abc"));
System.out.println(longestPalin("gggaaa"));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````given = 'ttaatta'
out = ""
single = ''

curChar = None
for x in sorted(given):
if curChar is None:
curChar = x
elif x == curChar:
out += x
curChar = None
else:
single = curChar
curChar = x

if curChar is not None:
single = curChar

print out + single + out[::-1]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// ZoomBA
def max_palindrome( string ){
// create a mapping of char -> count
cb = mset ( string.value )
#(m,M) = minmax( cb ) :: {
#(l,r) = \$.item ; (2 /? l.value) || (l.value < r.value) }
middle = (2 /? M.value) ? '' : str( M.key )
// generate palindrome by appending v to left and right
fold ( cb , middle ) -> {
// no need to take care of even n odd because, (2x+1)/2 -> x anyways
v = str( \$.item.key ) ** (\$.item.value /2 )
v + \$.partial + v
}
}
println ( max_palindrome( s ) )``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

A working solution in Python using recursion.

``````def longest_palindrome(string):
# count how many times each char shows up
count = {}
for char in string:
if char in count:
count[char] += 1
else:
count[char] = 1
# if there are multiple odds, leave only one odd
odd_appeared = False
odd_char = ""
for key in count:
if count[key] % 2 == 1:
if odd_appeared:
count[key] -= 1
else:
odd_appeared = True
odd_char = key
# go through the dictionary and reconstruct the palindrome string
palindrome = ""
for key in count:
chars = count[key]/2 * key
palindrome = palindrome + chars
palindrome = chars + palindrome
if odd_appeared:
n = len(palindrome)
palindrome = palindrome[:n/2] + odd_char + palindrome[n/2:]
return palindrome

print longest_palindrome('ttaatta')
print longest_palindrome('abc')
print longest_palindrome('aha')
print longest_palindrome('a')
print longest_palindrome('')``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````from collections import Counter
def longest_palin(string):
cntr = Counter(string)

odd = False
palin = ""
for letter, cnt in cntr.items():
palin = letter*(cnt/2) + palin + letter*(cnt/2)
if not odd and cnt%2:
mid = len(palin)/2
palin = palin[:mid] + letter + palin[mid:]
odd = True
return palin

print longest_palin("ttaatbcgdjakkjgdtaat")``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<iostream>
#include<string>
#include<list>
#include<unordered_map>

using namespace std;

list<char> generate_maximum_palindrom(const string& str){
list<char> palindrom {};
unordered_map<char, int> counter {};
int largest_odd = -1;
char largest_odd_char = ' ';

for(char c:str){
counter[c] ++;

if(counter[c] % 2 != 0 && counter[c] > largest_odd){
largest_odd_char = c;
largest_odd = counter[c];
}
}

if(largest_odd > -1){
while(counter[largest_odd_char]--){
palindrom.push_back(largest_odd_char);
}
}

for(auto it = counter.begin(); it != counter.end(); it++){
while(it->second >= 2){
palindrom.push_back(it->first);
palindrom.push_front(it->first);

it->second -= 2;
}
}

return palindrom;
}

int main(){

for(char c : generate_maximum_palindrom(str))
cout << c;
cout << endl;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Plain O(n).

Collect all char in a hash.
For each char in hash
if(hash.containsKey(char) > 1){
put that char in new string, i & strlen(str) - i position
update hash.add(char , (hash.containsKey(char) - 2))
} else {
int val = hash.get(char);
if(!hash.isempty()){
Error:-> Cannot be formed
}
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.