Validate a Bijective Substitution Cipher
Company: Remitly
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Validate a Bijective Substitution Cipher
Given a plaintext string and an encoded string of equal length, determine whether one consistent one-to-one character substitution maps the plaintext to the encoded text. Repeated plaintext characters must always map to the same encoded character, and two different plaintext characters may not map to the same encoded character.
## Function Contract
Implement `is_valid_substitution(plain, encoded) -> bool`.
## Constraints
- 0 <= string length <= 200000.
- Both strings contain only printable ASCII characters with code values from 32 through 126.
- Strings of different lengths are invalid.
- The mapping applies to every character, including whitespace and punctuation.
## Examples
```text
plain = "paper", encoded = "title"
output = true
```
```text
plain = "ab", encoded = "aa"
output = false
```
```hint Test repeated symbols
Include a repeated source character and a case where two different source characters would produce the same encoded character.
```
```hint Exercise the character boundary
Check empty strings, case differences, whitespace, and punctuation under the stated ASCII contract.
```
Quick Answer: Determine whether two printable-ASCII strings define a valid bijective character substitution. This coding interview problem tests consistent forward and reverse mappings, repeated characters, collisions, length mismatches, and linear-time reasoning across whitespace and punctuation.
Given a plaintext string `plain` and an encoded string `encoded`, return whether a single consistent one-to-one character substitution maps every character of `plain` to the character at the same position in `encoded`. Repeated plaintext characters must always map to the same encoded character, and two distinct plaintext characters must never map to the same encoded character. Return `false` when the strings have different lengths. Whitespace, punctuation, and letter case are significant.
Constraints
- 0 <= len(plain), len(encoded) <= 200000.
- Every character has an ASCII code from 32 through 126, inclusive.
- Strings with different lengths must return false; whitespace, punctuation, and letter case are significant.
Examples
Input: ('', '')
Expected Output: True
Explanation: Two empty strings admit the empty bijection.
Input: ('x', 'Q')
Expected Output: True
Explanation: A single source character can map to a single encoded character.
Hints
- Track what each plaintext character has already been assigned.
- A forward mapping alone cannot detect two different plaintext characters sharing one encoded character.
- Handle the length check before scanning corresponding positions.