Isomorphic Strings
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Strings s and t of equal length are isomorphic if the characters of s can be replaced to get t, where every
occurrence of a character is replaced by the same character, no two different characters map to the same character, and a
character may map to itself. Return whether s and t are isomorphic.
Examples
| s | t | result |
|---|---|---|
"egg" | "add" | true |
"foo" | "bar" | false |
"badc" | "baba" | false |
Example 3 — both b and d would have to map to b.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(s: string, t: string) → bool
Constraints
-
s.lengtht.length sandtconsist of English letters and digits; uppercase and lowercase are different characters.
Expected complexity
- Time
- O(N)
- Space
- O(alphabet)
Examples
| s | t | Expected |
|---|---|---|
"egg" | "add" | true |
"foo" | "bar" | false |
"badc" | "baba" | false |
Hint
Hint
Keep two maps: fwd (character of s → character of t) and back (the reverse). For each position, set the mapping if it is
empty, and return false if it conflicts. Checking only one direction misses two characters merging into one (example 3).
Arrays of size 128 suffice. Comparing every pair of positions is and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1000 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 4 | verdict only |