Validate word abbreviation and reconcile two abbreviations
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement a function isValidAbbreviation(word: string, abbr: string) that returns true if abbr is a valid abbreviation of word, where a positive integer in abbr represents the number of letters skipped and leading zeros are invalid. Follow-ups:
(a) Given two abbreviations abbr1 and abbr2, determine whether there exists at least one original word (over lowercase letters) that both could represent; if so, return true and output one possible alignment of kept/skipped positions, otherwise return false.
(b) Analyze time and space complexity, and discuss how you would handle very long inputs or streaming validation.
Quick Answer: Validate word abbreviation and reconcile two abbreviations evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Valid Word Abbreviation
Implement `isValidAbbreviation(word, abbr)` that returns `true` if `abbr` is a valid abbreviation of `word`.
An abbreviation replaces any number of consecutive characters with the count of characters replaced. A positive integer in `abbr` represents how many letters are skipped; the remaining characters in `abbr` must match `word` exactly, in order. Numbers must not contain leading zeros (e.g. `"01"`, `"s010n"` are invalid abbreviations), and the abbreviation is valid only if the two strings are fully consumed at the same time.
Example: `isValidAbbreviation("internationalization", "i12iz4n") = true` because `i` + skip 12 + `iz` + skip 4 + `n` reconstructs the word. `isValidAbbreviation("apple", "a2e") = false` because `a` + skip 2 lands on the 4th char (`l`), not `e`.
Use two pointers: walk `word` with `i` and `abbr` with `j`. On a letter in `abbr`, it must equal `word[i]` (advance both). On a digit, reject a leading `0`, parse the full number, and advance `i` by that count. Return `true` iff both pointers finish exactly at the end.
Constraints
- 1 <= word.length, but word and abbr may also be empty in edge cases.
- word consists of lowercase English letters.
- abbr consists of lowercase English letters and digits.
- Numbers in abbr have no leading zeros (a leading zero makes the abbreviation invalid).
- Parsed skip counts fit in a 32-bit / 64-bit integer.
Examples
Input: ("internationalization", "i12iz4n")
Expected Output: True
Explanation: i + skip 12 + iz + skip 4 + n exactly rebuilds the 20-letter word.
Input: ("apple", "a2e")
Expected Output: False
Explanation: a + skip 2 lands on index 3 ('l'), which does not match the required 'e'.
Hints
- Use two pointers, one over word and one over abbr, advancing them independently.
- When you hit a digit, parse the entire consecutive run of digits as one number, then jump that many positions in word.
- Reject the abbreviation immediately if a number starts with '0' (leading zeros are invalid).
- The abbreviation is valid only if BOTH pointers reach the end together — a number that runs past the end of word, or leftover characters, means invalid.
Reconcile Two Word Abbreviations
Follow-up to Valid Word Abbreviation. Given two abbreviation strings `abbr1` and `abbr2`, determine whether there exists at least one original word over lowercase letters that BOTH abbreviations could represent. Return `true` if such a word exists, otherwise `false`.
Each abbreviation uses the same rules as before: a positive integer (no leading zeros) means "skip that many letters" (a wildcard run that can stand for any letters), and a literal letter must appear at that exact position. Two abbreviations describe the same word iff they have the **same total length** and, at every position where BOTH pin down a concrete letter, those letters are equal. A skip in either abbreviation acts as a wildcard at that position.
Example: `canBothRepresentSameWord("a2c", "ab1c") = true` — both have length 4, abbr1 = a,_,_,c and abbr2 = a,b,_,c; no conflicting fixed letters, so a word like `"abxc"` works. `canBothRepresentSameWord("a2c", "a3c") = false` — lengths 4 vs 5 can never describe the same word.
Approach: expand each abbreviation into a per-position list where a literal contributes its character and a skip of k contributes k wildcard slots. If lengths differ, return `false`; otherwise return `false` only if some position has two differing fixed letters. Reject any abbreviation containing a leading-zero number.
Constraints
- abbr1 and abbr2 each follow the abbreviation grammar: lowercase letters and positive integers with no leading zeros.
- An abbreviation containing a leading-zero number is invalid and yields false.
- The original word, if it exists, is over lowercase English letters.
- Either abbreviation may be empty; two empty abbreviations both represent the empty word.
Examples
Input: ("a2c", "ab1c")
Expected Output: True
Explanation: Both length 4: a,_,_,c vs a,b,_,c. No conflicting fixed letters, so e.g. 'abxc' works.
Input: ("a2c", "a3c")
Expected Output: False
Explanation: Lengths 4 vs 5 differ, so no single word fits both.
Hints
- Think of each digit-run as a sequence of wildcard slots and each letter as a fixed slot, then line the two sequences up position by position.
- If the two abbreviations expand to different total lengths, no single word can satisfy both — return false.
- A conflict only happens when both abbreviations fix a concrete (and different) letter at the same position; a skip on either side is a wildcard that matches anything.
- Don't forget to reject abbreviations with leading zeros before comparing.