Quick Overview

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.

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/

Overview: 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

  1. A string can be permuted into a palindrome iff at most one character has an odd frequency.
  2. 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.
  3. For decimal addition, split into integer and fractional parts, pad fractional parts to equal length, add from right to left with carry.
  4. 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.

Loading coding console...

Show the approach

Approach

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