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.
Overview: 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.
Two strings are isomorphic when every character in `source` can be replaced
consistently to obtain `target`, 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.
Implement `areIsomorphic(source, target)`. Return `true` when the strings are isomorphic and `false`
otherwise.
### Rules
- Different lengths return `false`; two empty strings return `true`.
- Character identity is exact and case-sensitive: `'a'` and `'A'` are different characters.
- Spaces and punctuation are ordinary characters and participate in the mapping.
- A character is allowed to map to itself.
- Neither input string is modified.
### Example 1
```text
source = "egg"
target = "add"
result = true
```
`'e'` maps to `'a'` and `'g'` maps to `'d'`. No target character is claimed twice.
### Example 2
```text
source = "foo"
target = "bar"
result = false
```
`'o'` would have to map to both `'a'` and `'r'`.
### Example 3
```text
source = "paper"
target = "title"
result = true
```
`'p'` maps to `'t'`, `'a'` to `'i'`, `'e'` to `'l'`, and `'r'` to `'e'`. Both strings repeat a
character, and the repeats line up at the same positions.
### Example 4
```text
source = "ab"
target = "aa"
result = false
```
Each source character is individually consistent going forward, but `'a'` and `'b'` both claim the
target character `'a'`, which the definition forbids.
### Output
Return a Boolean. Every input has exactly one correct answer, so there is no ordering or
tie-breaking decision to make.
Constraints
- 0 <= source.length, target.length <= 90,000
- Each input contains only printable ASCII characters U+0020 through U+007E
- Character identity is exact and case-sensitive
- Spaces and punctuation are ordinary characters and participate in the mapping
- Different lengths return false; two empty strings return true
- Neither input string is modified
- Let B be the compact UTF-8 JSON byte length of [source, target], with no whitespace outside strings, where 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
Input: ('egg', 'add')
Expected Output: True
Input: ('foo', 'bar')
Expected Output: False
Hints
- Scan the two strings in lock step and decide, at each position, whether the pair you just read is compatible with every pair you have already committed to.
- Consistency from source to target is not enough: a rule that only records what each source character became will happily let two different source characters claim the same target character.
- The alphabet is fixed at 95 printable ASCII characters, so whatever bookkeeping you keep stays bounded no matter how long the strings get -- and it must survive across the whole scan, never being reset partway through.
Community answers
Answer by nisargshah1496
def areIsomorphic(source: str, target: str) -> bool:
"""Determine whether two strings have a consistent one-to-one character correspondence."""
if len(source) != len(target):
return False
s_to_t = {}
t_to_s = {}
for c1, c2 in zip(source, target):
if c1 in s_to_t and s_to_t[c1] != c2:
return False
if c2 in t_to_s and t_to_s[c2] != c1:
return False
s_to_t[c1] = c2
t_to_s[c2] = c1
return True