008 — Isomorphic Strings¶

Source¶

Original source: Classic hash map mapping exercise
Platform: LeetCode — https://leetcode.com/problems/isomorphic-strings/
Topic: hash map
Difficulty: Easy
Pattern: grouping / mapping
Basic idea inherited from: two synchronized dicts — দুটো dict একসাথে রেখে দুই-দিকের consistency রক্ষা

1. Problem in simple words¶

দুটো string s আর t দেওয়া আছে। বলো — এরা কি isomorphic? অর্থাৎ s-এর প্রতিটা অক্ষরকে কি এমন একটা নির্দিষ্ট অক্ষরে বদলে t বানানো যায়, যেখানে (১) একই অক্ষর সবসময় একই অক্ষরে যায়, আর (২) দুটো ভিন্ন অক্ষর কখনো একই অক্ষরে গিয়ে মেশে না?

s = "egg", t = "add"  →  True   (e→a, g→d, ধারাবাহিক)
s = "foo", t = "bar"  →  False  (o-কে একবার a, একবার r বানাতে হতো)

2. Which basic idea does this inherit from?¶

এটা দাঁড়িয়ে আছে two synchronized dicts-এর উপর — mapping/grouping (Pattern 3)-এর একটা রূপ। একটা dict রাখে s-এর অক্ষর → t-এর অক্ষর, আরেকটা রাখে উল্টোটা (t → s)। দুটো একসাথে রক্ষা করলে নিশ্চিত হয় mapping টা bijection (one-to-one, দুই দিকেই সঙ্গতিপূর্ণ)।

3. What is the hidden math or logic?¶

লুকানো logic একটা bijection (এক-এক মিল)। শুধু s → t map রাখলে "একই অক্ষর একই জায়গায় যায়" শর্তটা ধরা পড়ে, কিন্তু "দুটো অক্ষর এক জায়গায় মেশে না" শর্তটা ফসকে যায়। তাই উল্টো t → s map-ও লাগে। দুই map সবসময় সঙ্গতিপূর্ণ থাকলেই isomorphic — একটা invariant যা প্রতি অক্ষরে রক্ষা করতে হয়।

4. Which data structure is needed?¶

দুটো hash map (dict): s_to_t (s-এর অক্ষর → t-এর অক্ষর) আর t_to_s (উল্টোটা)। দুটো একসাথে দুই-দিকের mapping ধরে রাখে।

5. Why this data structure fits¶

প্রতিটা অক্ষরের mapping mনে রাখা আর "এই অক্ষর আগে অন্য কিছুতে map হয়েছিল কি?" — এই lookup গড়ে O(1)। তাই string জুড়ে একবার হেঁটেই consistency যাচাই হয়ে যায়। dict এই "key → তার নির্দিষ্ট partner" সম্পর্ক ধরে রাখার জন্য একদম তৈরি।

6. Real-life analogy¶

ভাবো একটা গোপন সংকেতলিপি (cipher), যেখানে প্রতিটা অক্ষর আরেকটা নির্দিষ্ট অক্ষরে বদলায় — A সবসময় হয় Q, B সবসময় হয় Z। নিয়ম দুটো: একই অক্ষর সবসময় একই বদলি পায়, আর দুটো ভিন্ন অক্ষর কখনো একই বদলি ভাগ করে না (নইলে decode করার সময় গুলিয়ে যাবে)। তোমার দুটো codebook — একটা encode-এর, একটা decode-এর — সবসময় মিলতে হবে।

7. Visual explanation¶

s = "egg", t = "add"। দুটো map গড়তে গড়তে এগোই:

জোড়া (e,a):  e নতুন, a নতুন  → s_to_t={e:a}, t_to_s={a:e}
জোড়া (g,d):  g নতুন, d নতুন  → s_to_t={e:a, g:d}, t_to_s={a:e, d:g}
জোড়া (g,d):  e→? না, g→d আছে, d→g আছে, সঙ্গতিপূর্ণ  → ঠিক আছে
সব মিলল  →  return True

আর conflict হলে (s="foo", t="bar"):

(f,b): নতুন → s_to_t={f:b}, t_to_s={b:f}
(o,a): নতুন → s_to_t={f:b, o:a}, t_to_s={b:f, a:o}
(o,r): o আগে a-তে map হয়েছিল, এখন r চাইছে → conflict → return False

8. Example input and output¶

Input : s = "egg",   t = "add"     Output: True
Input : s = "foo",   t = "bar"     Output: False
Input : s = "paper", t = "title"   Output: True
Edge  : s = "badc",  t = "baba"    Output: False  (d আর c দুটোই b/a-তে মেশে)
Edge  : s = "",      t = ""        Output: True   (দুটোই খালি)

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা অক্ষরের জন্য মনে মনে ভেবে দেখি আগে কোথাও আলাদা mapping হয়েছিল কি না — অর্থাৎ প্রতিবার পুরো ইতিহাস ঘেঁটে দেখা।

প্রতিটা position i-র জন্য:
    s[i] কি আগে অন্য কোনো t-অক্ষরে map হয়েছিল?  (পেছনের সব position খুঁজি)
    t[i] কি আগে অন্য কোনো s-অক্ষরে এসেছিল?       (আবার খুঁজি)
        গরমিল পেলে → return False
return True

10. Why brute force is slow¶

প্রতিটা position-এ আগের সব position আবার ঘাঁটা = মোট O(n^2)। অথচ mapping দুটো dict-এ জমিয়ে রাখলে "আগে কোথায় map হয়েছিল" প্রশ্নের উত্তর O(1)-এ পাওয়া যায়। বারবার ইতিহাস scan করাই অপচয়।

11. Key observation¶

মূল observation: isomorphic হতে হলে mapping টা দুই-দিকেই এক-এক হতে হবে। তাই দুটো dict — s→t আর t→s — একসাথে রক্ষা করলে দুটো শর্তই (consistency + কোনো merge নয়) এক পাসে ধরা পড়ে।

12. Optimized intuition¶

s আর t-কে position-ধরে জোড়ায় জোড়ায় (zip) হাঁটো। প্রতিটা জোড়া (a, b)-তে দেখো: a আগে map হয়ে থাকলে সেটা কি b-তেই? আর b আগে এসে থাকলে সেটা কি a থেকেই? দুটোর কোনোটা না মিললে False। মিললে দুই dict-এ mapping টা রেখে এগোও। পুরো string শেষ হলে True।

13. Thinking tweak¶

মোচড়: এক-দিকের map যথেষ্ট মনে হলেও আসলে নয় — "দুটো অক্ষর এক জায়গায় মেশা" ঠেকাতে উল্টো map-ও লাগে। দুটো synchronized dict রাখলেই bijection-এর দুই শর্ত একসাথে রক্ষা পায়।

14. Step-by-step dry run¶

Input s = "foo", t = "bar":

length: 3 == 3 → এগোও; s_to_t = {}, t_to_s = {}।
জোড়া (f, b): কেউ আগে নেই → s_to_t = {f:b}, t_to_s = {b:f}।
জোড়া (o, a): কেউ আগে নেই → s_to_t = {f:b, o:a}, t_to_s = {b:f, a:o}।
জোড়া (o, r): o আগে a-তে map হয়েছিল, এখন চাইছে r (a != r) → return False।

15. Python solution¶

def is_isomorphic(s, t):
    if len(s) != len(t):
        return False
    s_to_t = {}
    t_to_s = {}
    for a, b in zip(s, t):
        if a in s_to_t and s_to_t[a] != b:   # s-অক্ষর আগে অন্যত্র map হয়েছিল?
            return False
        if b in t_to_s and t_to_s[b] != a:   # t-অক্ষর আগে অন্য কেউ দখল করেছিল?
            return False
        s_to_t[a] = b
        t_to_s[b] = a
    return True

# ---- tests ----
assert is_isomorphic("egg", "add") == True
assert is_isomorphic("foo", "bar") == False
assert is_isomorphic("paper", "title") == True
assert is_isomorphic("badc", "baba") == False
assert is_isomorphic("", "") == True
print("সব test pass!")

16. Line-by-line code explanation¶

if len(s) != len(t): return False — আলাদা দৈর্ঘ্যে position-wise mapping সম্ভবই নয়।
s_to_t, t_to_s — দুই-দিকের codebook; একটা s→t, একটা t→s।
for a, b in zip(s, t) — একই position-এর অক্ষর-জোড়া একসাথে নিই।
if a in s_to_t and s_to_t[a] != b — a আগে map হয়ে থাকলে সেটা কি এখনকার b-র সাথে মেলে? না মিললে consistency ভাঙল।
if b in t_to_s and t_to_s[b] != a — b আগে অন্য কোনো অক্ষর দখল করেছিল কি? করলে দুই অক্ষর এক জায়গায় মিশছে — নিষিদ্ধ।
s_to_t[a] = b / t_to_s[b] = a — দুই dict-এ mapping টা রেখে দাও।
return True — পুরো string জুড়ে কোনো conflict না হলে isomorphic।

17. Output walkthrough¶

"egg","add": e↔a, g↔d ধারাবাহিক → True। "foo","bar": দ্বিতীয় o আগের a-mapping ভাঙে → False। "paper","title": p↔t, a↔i, e↔l, r↔e সব এক-এক → True। "badc","baba": d-কে b-তে map করতে গেলে b আগেই b-র দখলে — conflict → False। দুই খালি string → loop চলে না → True। শেষে print: সব test pass!।

18. Time complexity¶

O(n) — string-এর উপর একবার হাঁটি, প্রতি অক্ষরে dict operation গড়ে O(1)।

19. Space complexity¶

O(k) — k = distinct অক্ষরের সংখ্যা, দুই dict-এ জমে (alphabet সীমিত হলে কার্যত O(1))।

20. Common mistakes¶

শুধু এক dict (s→t) রাখা — তখন "badc"/"baba"-র মতো case ধরা পড়ে না, কারণ দুটো ভিন্ন s-অক্ষর একই t-অক্ষরে মেশা ঠেকানো যায় না।
length check বাদ দেওয়া — zip ছোট string-এ থেমে যায়, তাই বড়টার বাকি অংশ পরীক্ষাই হয় না।
consistency check-এর আগে mapping লিখে ফেলা — তখন এই-position-এর mapping দিয়েই নিজেকে যাচাই করে ভুল pass দেয়; আগে check, পরে লেখো।

21. Which basic problem this inherits from¶

ভিত্তি: mapping/grouping (Pattern 3) — তবে এখানে canonical key নয়, two synchronized dicts দিয়ে bijection রক্ষা। ../patterns.md-র Pattern 3 আর ../operations.md-র dict-mapping অংশ দেখো।

22. Similar harder problems¶

Word Pattern — https://leetcode.com/problems/word-pattern/ (অক্ষর ↔ শব্দ, একই two-map idea)
Group Anagrams — https://leetcode.com/problems/group-anagrams/ (এই tracker-এর #10; canonical key দিয়ে grouping)
Find and Replace Pattern — https://leetcode.com/problems/find-and-replace-pattern/ (একাধিক word-এ isomorphism)

23. Pattern learned¶

Two synchronized dicts (bijection): এক-এক mapping যাচাই করতে দুই দিকের dict একসাথে রাখো — এক দিকের map কখনোই যথেষ্ট নয়।

24. Final summary¶

ভবিষ্যতের আমাকে: "একটা থেকে আরেকটা consistent mapping / এক-এক বদলি / pattern মেলে কি" শুনলেই দুটো dict — সামনে আর পেছনে। এক দিকের map ভুলিয়ে দেবে; bijection-এর দুই শর্ত রক্ষা করতে দুই-দিকের সঙ্গতি লাগবেই।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।