CareerCup

O(len(s)^2) memory, runtime.

import collections

def solve(s):
    dp = {}
    previous = {}
    def dfs(l, r):
        result = dp.get((l, r))
        if result is not None:
            return result
        if l >= r - 1:
            result = 0
        else:
            candidates = [
                ((l + 1, r), (r, s[l], True)),
                ((l, r - 1), (l, s[r - 1], False))
            ]
            if s[l] == s[r - 1]:
                candidates.append(((l + 1, r - 1), None))
            min_score = len(s)
            best_cand = None
            for (nl, nr), action in candidates:
                score = dfs(nl, nr)
                if score < min_score:
                    min_score = score
                    best_cand = ((nl, nr), action)
            previous[(l, r)] = best_cand
            result = min_score + (0 if best_cand[1] is None else 1)
        dp[(l, r)] = result
        return result
    dfs(0, len(s))
    actions = []
    cur = (0, len(s))
    while True:
        res = previous.get(cur)
        if res is None:
            break
        next_cur, action = res
        if action is not None:
            actions.append(action)
        cur = next_cur
    return actions

def check(s):
    actions = solve(s)
    s = list(s)
    insert_at = [collections.deque() for i in xrange(len(s) + 1)]

    for pos, char, front in actions:
        if front:
            insert_at[pos].appendleft(char)
        else:
            insert_at[pos].append(char)
    for pos, chars in reversed(list(enumerate(insert_at))):
        if chars:
            s[pos:pos] = ''.join(chars)
    assert s == s[::-1], ''.join(s)
    return ''.join(s)

print check('pototp')
print check('oto maym oto')
print check('a lazy fox jumps overy a lazy')

import java.util.HashMap;
import java.util.Map.Entry;

public class NeeedtoMakePalindrome {

public static void main(String[] args) {
// TODO Auto-generated method stub

String s = "aabbbccddee";

// if string is of even length then frequenecy of all chars should be
// even.
// if string is odd length than atmost one char can have odd frequency
// aabcc(correct, a palidrome can be made out of this pattern)
// aaabbef(not a palindrome)
HashMap<Character, Integer> hm = new HashMap<>();
int len = s.length();
for (char ch : s.toCharArray()) {
if (hm.containsKey(ch)) {
hm.put(ch, hm.get(ch) + 1);
} else {
hm.put(ch, 1);
}
}
HashMap<Character, Integer> paddingmap = new HashMap<>();

int totalpaddingneeded = 0;

if (len % 2 == 0) {
for (Entry<Character, Integer> entry : hm.entrySet()) {
Integer value = entry.getValue();
totalpaddingneeded = 0;
if (value % 2 == 1) {
totalpaddingneeded += 1;
paddingmap.put(entry.getKey(), totalpaddingneeded);
}
}

if (paddingmap.size() > 0) {
for (Entry<Character, Integer> entry : paddingmap.entrySet()) {
System.out.println(entry.getKey() + ">>>needed to apppened"
+ ">>>" + entry.getValue() + ">>>" + "times");
}
} else {
System.out.println("Already palindrome can be construcuted");
}

}

else {
System.out.println("when length is odd");
int count = 0;
for (Entry<Character, Integer> entry : hm.entrySet()) {
Integer value = entry.getValue();
totalpaddingneeded = 0;

if (value % 2 == 1) {
count++;
if (count >= 1) {
totalpaddingneeded += 1;
paddingmap.put(entry.getKey(), totalpaddingneeded);
}
}
}

if (paddingmap.size() > 0) {
for (Entry<Character, Integer> entry : paddingmap.entrySet()) {
System.out.println(entry.getKey() + ">>>needed to apppened"
+ ">>>" + entry.getValue() + ">>>" + "times");
}}}}}

import java.util.HashMap;
import java.util.Map.Entry;

public class NeeedtoMakePalindrome {

public static void main(String[] args) {
// TODO Auto-generated method stub

String s = "aabbbccddee";

// if string is of even length then frequenecy of all chars should be
// even.
// if string is odd length than atmost one char can have odd frequency
// aabcc(correct, a palidrome can be made out of this pattern)
// aaabbef(not a palindrome)
HashMap<Character, Integer> hm = new HashMap<>();
int len = s.length();
for (char ch : s.toCharArray()) {
if (hm.containsKey(ch)) {
hm.put(ch, hm.get(ch) + 1);
} else {
hm.put(ch, 1);
}
}
HashMap<Character, Integer> paddingmap = new HashMap<>();

int totalpaddingneeded = 0;

if (len % 2 == 0) {
for (Entry<Character, Integer> entry : hm.entrySet()) {
Integer value = entry.getValue();
totalpaddingneeded = 0;
if (value % 2 == 1) {
totalpaddingneeded += 1;
paddingmap.put(entry.getKey(), totalpaddingneeded);
}
}

if (paddingmap.size() > 0) {
for (Entry<Character, Integer> entry : paddingmap.entrySet()) {
System.out.println(entry.getKey() + ">>>needed to apppened"
+ ">>>" + entry.getValue() + ">>>" + "times");
}
} else {
System.out.println("Already palindrome can be construcuted");
}

}

else {
System.out.println("when length is odd");
int count = 0;
for (Entry<Character, Integer> entry : hm.entrySet()) {
Integer value = entry.getValue();
totalpaddingneeded = 0;

if (value % 2 == 1) {
count++;
if (count >= 1) {
totalpaddingneeded += 1;
paddingmap.put(entry.getKey(), totalpaddingneeded);
}
}
}

if (paddingmap.size() > 0) {
for (Entry<Character, Integer> entry : paddingmap.entrySet()) {
System.out.println(entry.getKey() + ">>>needed to apppened"
+ ">>>" + entry.getValue() + ">>>" + "times");
}
}
}
}
}