Funcia
Lv.1hashstring

Isomorphic Strings

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

stresult
"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

  • 1≤1 \le s.length == t.length ≤200,000\le 200{,}000
  • s and t consist of English letters and digits; uppercase and lowercase are different characters.

Expected complexity

Time
O(N)
Space
O(alphabet)

Examples

stExpected
"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 O(N2)O(N^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.