Check Palindrome and Add Decimal Strings
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
LeetCode 266. Palindrome Permutation – Given a string, determine whether any permutation can form a palindrome. Follow-up: If a palindrome permutation exists, generate and return one such palindrome. Implement addition of two non-negative decimal numbers represented as strings (the numbers may contain a decimal point) without using built-in arbitrary-precision types.
https://leetcode.com/problems/palindrome-permutation/description/
Quick Answer: This question evaluates string-processing and numeric representation competencies, focusing on character-frequency reasoning for palindrome permutation detection and implementation of arbitrary-precision addition for decimal strings.
Given a string s of lowercase English letters and two non-negative decimal numbers a and b as strings (each may contain at most one decimal point), perform two tasks: (1) Determine if any permutation of s can form a palindrome. If yes, return the lexicographically smallest palindrome permutation; otherwise return an empty string. (2) Return the sum of a and b as a canonical decimal string computed without using built-in arbitrary-precision numeric types. Canonical means: no leading zeros in the integer part (except "0"), no trailing zeros in the fractional part, and omit the decimal point if the fractional part is empty. Return a dictionary with keys: palindrome_possible (bool), palindrome (string), and sum (string).
Constraints
- 1 <= len(s) <= 200000
- s consists only of lowercase English letters 'a' to 'z'
- 1 <= len(a), len(b) <= 100000
- a and b match regex: ^\d+(\.\d+)?$ (no sign, no thousand separators)
- Numbers are non-negative
- Do not use built-in big integers/decimals for addition; implement digit-by-digit string addition
- Return the lexicographically smallest palindrome if possible; otherwise return empty string
Solution
from typing import Dict
def check_palindrome_and_add(s: str, a: str, b: str) -> dict:
# Part 1: Lexicographically smallest palindrome permutation check and construction
# Count frequencies (only lowercase letters by constraint)
counts = [0] * 26
for ch in s:
counts[ord(ch) - 97] += 1
odd_cnt = sum(1 for c in counts if c % 2 == 1)
possible = odd_cnt <= 1
palindrome = ""
if possible:
half_parts = []
center = ""
for i in range(26):
c = counts[i]
if c % 2 == 1:
center = chr(97 + i)
if c // 2:
half_parts.append(chr(97 + i) * (c // 2))
first_half = "".join(half_parts)
palindrome = first_half + center + first_half[::-1]
# Part 2: Add two non-negative decimal strings without big integers
def split_num(x: str):
if '.' in x:
ip, fp = x.split('.', 1)
else:
ip, fp = x, ''
return ip, fp
def add_decimal_strings(x: str, y: str) -> str:
xi, xf = split_num(x)
yi, yf = split_num(y)
# Pad fractional parts to equal length
L = max(len(xf), len(yf))
if L:
xf = xf + '0' * (L - len(xf))
yf = yf + '0' * (L - len(yf))
carry = 0
# Add fractional part
frac_res = []
for i in range(L - 1, -1, -1):
da = ord(xf[i]) - 48 if L else 0
db = ord(yf[i]) - 48 if L else 0
ssum = da + db + carry
frac_res.append(chr((ssum % 10) + 48))
carry = ssum // 10
frac_res.reverse()
frac = ''.join(frac_res) if L else ''
# Add integer part
i, j = len(xi) - 1, len(yi) - 1
int_res = []
while i >= 0 or j >= 0 or carry:
da = ord(xi[i]) - 48 if i >= 0 else 0
db = ord(yi[j]) - 48 if j >= 0 else 0
ssum = da + db + carry
int_res.append(chr((ssum % 10) + 48))
carry = ssum // 10
i -= 1
j -= 1
int_res.reverse()
ip = ''.join(int_res)
# Normalize
ip = ip.lstrip('0') or '0'
if frac:
frac = frac.rstrip('0')
if frac:
return ip + '.' + frac
else:
return ip
summed = add_decimal_strings(a, b)
return {
'palindrome_possible': possible,
'palindrome': palindrome if possible else '',
'sum': summed
}
Explanation
We count letter frequencies to determine if a palindrome permutation is possible: at most one character may have an odd count. To construct the lexicographically smallest palindrome, we append floor(count/2) copies of each character in ascending order to form the first half, put the (single) odd-count character in the center if present, and mirror the first half. For decimal addition, we split the inputs at the decimal point, right-pad the fractional parts to equal length, add the fractional parts from right to left with carry, then add the integer parts similarly. Finally we normalize by stripping integer leading zeros and fractional trailing zeros, and removing the decimal point if the fractional part becomes empty.
Time complexity: O(n + m + k), where n = len(s), m = len(a), k = len(b). Space complexity: O(26 + max(m, k)) extra space, excluding the output strings.
Hints
- A string can be permuted into a palindrome iff at most one character has an odd frequency.
- To get the lexicographically smallest palindrome, build the first half by placing characters in ascending order, use the single odd-count character as the center (if any), and mirror the first half.
- For decimal addition, split into integer and fractional parts, pad fractional parts to equal length, add from right to left with carry.
- Normalize the result: strip leading zeros in the integer part (leave at least one zero), strip trailing zeros in the fractional part, and drop the decimal point if the fractional part becomes empty.