Count Spellings Using Chemical Element Symbols
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Count Spellings Using Chemical Element Symbols
## Problem
Given a list of valid chemical element symbols and a target word, count how many distinct ways the entire word can be segmented into symbols. Matching is case-insensitive, symbols may be reused, and different boundary placements count as different spellings.
Implement:
```python
def count_symbol_spellings(symbols: list[str], word: str) -> int:
...
```
The input symbol list is the complete source of truth; the function must not rely on a built-in periodic table.
## Constraints
- `1 <= len(symbols) <= 200`
- Every symbol contains one or two ASCII letters.
- Symbols are unique under case-insensitive comparison.
- `0 <= len(word) <= 100_000`
- `word` contains only ASCII letters.
- Return an arbitrary-precision integer.
- The empty word has one valid spelling: choose no symbols.
## Example
```python
symbols = ["P", "H", "Y", "Si", "C", "S", "Cs", "I"]
count_symbol_spellings(symbols, "Physics")
```
The result is `4`, corresponding to these boundary choices:
```text
P-H-Y-Si-C-S
P-H-Y-Si-Cs
P-H-Y-S-I-C-S
P-H-Y-S-I-Cs
```
## Performance Goal
Avoid enumerating and storing every complete spelling. State the time and auxiliary-space complexity of your approach.
Quick Answer: Count how many ways a word can be segmented into supplied one- or two-letter chemical element symbols. Design a case-insensitive dynamic program that supports symbol reuse, arbitrary-precision counts, and a 100,000-character target without enumerating spellings.
Count the distinct full segmentations of a word into supplied one- or two-letter chemical symbols. Matching is case-insensitive, symbols may be reused, and boundary choices distinguish spellings.
Constraints
- There are at most 200 unique case-insensitive symbols.
- Each symbol contains one or two ASCII letters.
- The word contains only ASCII letters and may have length 100,000.
- The empty word has one spelling.
Examples
Input: {'symbols':['P','H','Y','Si','C','S','Cs','I'],'word':'Physics'}
Expected Output: 4
Explanation: The supplied word has four boundary patterns.
Input: {'symbols':['A','Aa'],'word':'aaa'}
Expected Output: 3
Explanation: One- and two-letter choices yield three segmentations.
Hints
- Dynamic programming needs only the counts one and two positions back.
- Normalize both symbols and word to one case once.