Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
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;
}
}
//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();
}
}
#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;
}
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
var stringToAdd:String! = ""
while (letterCount > 0) {
stringToAdd = stringToAdd.stringByAppendingString(letter)
letterCount -= 1
}
leftString = stringToAdd + leftString
rightString = rightString + stringToAdd
}
}
}
return leftString + centerString + rightString
}
makePalindrome("aha") // "aha"
makePalindrome("ttaatta") // "ttaaatt"
makePalindrome("abc") // "b"
makePalindrome("gggaaa") // "gaaag"
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
var stringToAdd:String! = ""
while (letterCount > 0) {
stringToAdd = stringToAdd.stringByAppendingString(letter)
letterCount -= 1
}
leftString = stringToAdd + leftString
rightString = rightString + stringToAdd
}
}
}
return leftString + centerString + rightString
}
makePalindrome("aha") // "aha"
makePalindrome("ttaatta") // "ttaaatt"
makePalindrome("abc") // "b"
makePalindrome("gggaaa") // "gaaag"
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]
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
#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;
}
#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;
}
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;
}
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());
}
}
def get_polindrom(s):
d = collections.defaultdict(int)
for char in s:
d[char] += 1
result = []
odd_added = False
for k, v in d.items():
if not odd_added:
if v % 2 != 0:
odd_added = True
result = result[:(len(result)/2)] + [k] * v + result[(len(result)/2):]
else:
result += [k] * (v // 2)
result = [k] * (v // 2) + result
return "".join(result)
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");
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");
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
/*
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();
}
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"));
}
}
// 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
}
}
s = 'akjhadajsoadjaoiwjewaodjaosid'
println ( max_palindrome( s ) )
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('')
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")
#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(){
string str = "akjhadajsoadjaoiwjewaodjaosid";
for(char c : generate_maximum_palindrom(str))
cout << c;
cout << endl;
}
Really a google question ?
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);
hash.add(char, hash.containsKey(char) - 1);
if(!hash.isempty()){
Error:-> Cannot be formed
}
}
- Luke Rhinehart July 22, 2016