Determine Whether Two Strings Are Isomorphic
Company: Remitly
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
## Determine Whether Two Strings Are Isomorphic
### Problem
Implement `areIsomorphic(source, target) -> result`.
Two strings are isomorphic when every character in `source` can be replaced consistently to obtain `target`, while preserving position. Each source character must map to exactly one target character, and two different source characters may not map to the same target character.
Return `true` when the strings are isomorphic and `false` otherwise.
### Function Contract
- Python: `def areIsomorphic(source: str, target: str) -> bool`
- JavaScript: `function areIsomorphic(source, target)` returns a Boolean.
- Java: `boolean areIsomorphic(String source, String target)`
- C++: `bool areIsomorphic(const string& source, const string& target)`
### Portable Contract
- Each input contains only printable ASCII characters U+0020 through U+007E.
- `0 <= source.length, target.length <= 90,000`.
- Different lengths return `false`; two empty strings return `true`.
- Character identity is exact and case-sensitive.
- Spaces and punctuation are ordinary characters and participate in the mapping.
- Do not modify either string.
- Let `B` be the compact UTF-8 JSON byte length of `[source,target]`, with no whitespace outside strings. Quotes and reverse solidus characters use their shortest required JSON escapes, and every bracket, comma, quote, escape, and character byte is counted. Inputs satisfy `B <= 96,000`.
- The serialized Boolean result uses four or five bytes, so input plus output is at most `96,005` bytes.
- Target `O(source.length + target.length)` time and `O(1)` auxiliary space for the fixed printable-ASCII alphabet.
### Examples
```text
source = "egg"
target = "add"
result = true
```
```text
source = "foo"
target = "bar"
result = false
```
```text
source = "paper"
target = "title"
result = true
```
```text
source = "ab"
target = "aa"
result = false
```
```hint Check the relationship in both directions
Consistency from source to target is not enough when two distinct source characters try to claim the same target character.
```
### Discussion Requirements
1. State the invariant maintained after processing each aligned character pair.
2. Explain why one forward map alone accepts an invalid many-to-one mapping.
3. Cover empty strings, unequal lengths, repeated characters, spaces, punctuation, and case differences.
4. Explain how fixed-size ASCII tables keep memory constant as input grows.
5. Describe how to process very large strings in synchronized chunks without resetting mapping state between chunks.
Quick Answer: Decide whether two strings have a consistent one-to-one character correspondence at every position. The exercise tests bidirectional mapping invariants, printable ASCII edge cases, constant-space reasoning, and scalable processing of large inputs.