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
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.