Skip to content

008 — Smallest String With Swaps

Source

  • Original source: Classic grouping-then-sorting exercise
  • Platform: LeetCode — https://leetcode.com/problems/smallest-string-with-swaps/
  • Topic: disjoint set union
  • Difficulty: Medium
  • Pattern: group then sort inside groups
  • Basic idea inherited from: 10-এর grouping pattern + 02-arrays-and-strings-এর sorting; index union করে group বানাও, প্রতি group-এর ভেতরে char sort করো

1. Problem in simple words

একটা string s আর কতগুলো index-pair pairs দেওয়া; প্রতিটা pair [a, b] মানে s[a] আর s[b] তুমি যতবার খুশি swap করতে পারো। এই swap-গুলো দিয়ে বানানো যায় এমন lexicographically smallest string-টা বের করো।

s = "dcab",  pairs = (0-3) (1-2)
        index {0,3} নিজেদের মধ্যে swap করা যায়, {1,2}-ও
        {0,3}: 'd','b' -> sort -> 'b','d';  {1,2}: 'c','a' -> sort -> 'a','c'
        ফল  ->  "bacd"

2. Which basic idea does this inherit from?

দুটো ভিত একসাথে: এই tracker-এর grouping pattern (Pattern D) — যেসব index একে অপরের সাথে (সরাসরি বা ঘুরিয়ে) swap করা যায়, তারা এক group; আর ../../02-arrays-and-strings/-এর sorting — প্রতিটা group-এর ভেতরে যেহেতু char-গুলো যেকোনো বিন্যাসে সাজানো যায়, তাই sort করলেই ওই position-গুলোয় smallest বিন্যাস বসে।

3. What is the hidden math or logic?

লুকানো logic দুই ধাপে:

  • swap transitivity: যদি (a,b) আর (b,c) swap করা যায়, তাহলে a, b, c-র char-গুলো নিজেদের মধ্যে যেকোনো order-এ সাজানো যায় — কারণ বারবার swap দিয়ে যেকোনো permutation পাওয়া সম্ভব। তাই connected index-রা একটা equivalence class।
  • lexicographic optimum: একটা group-এর char-গুলো যদি যেকোনো order-এ বসানো যায়, তাহলে smallest পেতে হলে ছোট char-গুলো ছোট index-এ বসাও — অর্থাৎ index গুলো sorted, char গুলোও sorted, তারপর জোড়া মেলাও।

4. Which data structure is needed?

একটা DSU (parent + size array) string-এর length-সমান, প্লাস প্রতি root-এ তার group-এর index জড়ো করার জন্য একটা dictionary/map। DSU দিয়ে group বানাও, map দিয়ে group-প্রতি char sort করে বসাও।

5. Why this data structure fits

প্রশ্নের কেন্দ্র — "কোন index-গুলো এক সাথে নাড়াচাড়া করা যায়?" — ঠিক DSU-র grouping প্রশ্ন। swap relation reflexive/symmetric/transitive, তাই index-রা equivalence class-এ ভাগ হয়। DSU সেই class-গুলো near-constant time-এ গড়ে; তারপর প্রতি class-এ sorting বাকি কাজ সারে।

6. Real-life analogy

ভাবো কয়েকটা আলাদা box, প্রতিটা box-এ কিছু চিঠি (tiles) আছে — যেগুলো তুমি ওই box-এর ভেতরে যেমন খুশি সাজাতে পারো, কিন্তু এক box থেকে অন্য box-এ সরাতে পারো না। swap-pair গুলো বলে দেয় কোন position-গুলো একই box-এ। সবচেয়ে "ছোট" শব্দ পেতে হলে প্রতিটা box-এর tiles বর্ণানুক্রমে সাজিয়ে box-এর position-গুলোয় বাঁ থেকে ডানে বসাও।

7. Visual explanation

index union করে group; প্রতি group-এর char sort করে, group-এর sorted index-এ বসাও।

s = "dcab",  pairs: (0-3) (1-2)

index:    0   1   2   3
char:    'd' 'c' 'a' 'b'

union(0,3):  group {0,3}
union(1,2):  group {1,2}

group {0,3}: chars at [0,3] = ['d','b'] -> sorted ['b','d']
             sorted index [0,3] <- ['b','d']   =>  s[0]='b', s[3]='d'

group {1,2}: chars at [1,2] = ['c','a'] -> sorted ['a','c']
             sorted index [1,2] <- ['a','c']   =>  s[1]='a', s[2]='c'

ফল: index 0  1  2  3
        char 'b''a''c''d'   ->  "bacd"

------ একটা group হলে: pairs (0-3)(1-2)(0-2) ------
union গুলো 0,1,2,3 সব এক group -> chars ['d','c','a','b'] sorted ['a','b','c','d']
sorted index [0,1,2,3] <- ['a','b','c','d']  ->  "abcd"

8. Example input and output

Input : s="dcab", pairs=[[0,3],[1,2]]
Output: "bacd"

Input : s="dcab", pairs=[[0,3],[1,2],[0,2]]
Output: "abcd"     (সব index এক group)

Input : s="cba", pairs=[[0,1],[1,2]]
Output: "abc"

Edge case (no pairs): s="abc", pairs=[]  ->  "abc"  (কিছুই swap করা যায় না)

9. Brute force thinking

সরল চিন্তা: pairs দিয়ে যে যে string-এ পৌঁছানো যায় তার সবগুলো generate করো (বারবার swap চালিয়ে, BFS-এর মতো reachable states ছড়িয়ে), তারপর সবচেয়ে ছোটটা নাও।

1) শুরু string থেকে প্রতিটা swap প্রয়োগ করে নতুন state বানাও
2) সব reachable state একটা set-এ জড়ো করো (BFS)
3) সব state-এর মধ্যে lexicographically smallest-টা ফেরাও

10. Why brute force is slow

Reachable states-এর সংখ্যা group-size-এর factorial পর্যন্ত যেতে পারে — n বড় হলে বিস্ফোরক, সম্পূর্ণ অবাস্তব। DSU পথটা ছোট করে: আসল permutation generate করার দরকারই নেই — শুধু group বের করো (O(P·α)) আর প্রতি group-এ একটা sort (মোট O(n log n))। তাই exponential থেকে near-linear-এ নামে।

11. Key observation

মূল observation: একই group-এর char-গুলো যেকোনো order-এ সাজানো যায়। তাই আসল swap-sequence খোঁজার দরকার নেই — শুধু কোন index-রা এক group, সেটা জানো; তারপর প্রতি group-এ char sort করে sorted index-এ বসাও — সেটাই lexicographic minimum, কারণ ছোট char ছোট index-এ যায়।

12. Optimized intuition

length-সমান DSU নাও; প্রতিটা pair union করো। তারপর find(i) দিয়ে index-গুলোকে group-এ bucket করো (dictionary)। প্রতি group-এর index গুলো sort করো, ওই position-এর char গুলোও sort করো, তারপর জোড়ায় জোড়ায় বসাও (ছোট index ← ছোট char)। সব মিলিয়ে O(n log n + P·α)।

13. Thinking tweak

মোচড়: "কোন swap-গুলো কোন order-এ চালালে smallest পাব?" — এই swap-sequence খোঁজার চিন্তা ছাড়ো। বদলে ভাবো "কোন position-গুলো একই box-এ, সেটা বের করি; তারপর প্রতি box-এ char-গুলো sort করে বসিয়ে দিই।" Process (swap) থেকে structure (group)-এ চিন্তা সরানোই চাবি।

14. Step-by-step dry run

Input s="dcab", pairs=[[0,3],[1,2]]:

  1. union(0,3) → group {0,3}; union(1,2) → group {1,2}
  2. bucket: find(0)=find(3) → {0,3} এক bucket; find(1)=find(2) → {1,2} আরেক bucket
  3. bucket {0,3}: char ['d','b'] → sorted ['b','d']; sorted index [0,3] → s[0]='b', s[3]='d'
  4. bucket {1,2}: char ['c','a'] → sorted ['a','c']; sorted index [1,2] → s[1]='a', s[2]='c'
  5. ফল: "bacd"

15. Python solution

from collections import defaultdict


class DSU:
    def __init__(self, n):
        self.parent = list(range(n))     # প্রথমে সবাই নিজের নিজের root
        self.size = [1] * n              # প্রতিটা group-এ একজন

    def find(self, x):                   # representative + path compression
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x

    def union(self, x, y):               # union by size; merge হলে True
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx              # rx এখন বড় root
        self.parent[ry] = rx            # ছোটটা বড়টার নিচে ঝোলে
        self.size[rx] += self.size[ry]
        return True


def smallest_string_with_swaps(s, pairs):
    n = len(s)
    dsu = DSU(n)
    for a, b in pairs:
        dsu.union(a, b)                  # swap করা যায় এমন index এক group

    groups = defaultdict(list)
    for i in range(n):
        groups[dsu.find(i)].append(i)    # প্রতি root-এ তার index গুলো জড়ো

    res = list(s)
    for idxs in groups.values():
        chars = sorted(res[i] for i in idxs)     # group-এর char sort
        for i, c in zip(sorted(idxs), chars):    # ছোট index <- ছোট char
            res[i] = c
    return "".join(res)


# ---- tests ----
assert smallest_string_with_swaps("dcab", [[0, 3], [1, 2]]) == "bacd"
assert smallest_string_with_swaps("dcab", [[0, 3], [1, 2], [0, 2]]) == "abcd"
assert smallest_string_with_swaps("cba", [[0, 1], [1, 2]]) == "abc"
assert smallest_string_with_swaps("abc", []) == "abc"      # কোনো swap নেই
print("সব test pass!")

16. Line-by-line code explanation

  • for a, b in pairs: dsu.union(a, b) — প্রতিটা swap-pair দুটো index এক group-এ মেলায়; transitivity-তে সব reachable index এক হয়ে যায়।
  • groups[dsu.find(i)].append(i) — প্রতিটা index-কে তার representative-এর bucket-এ ফেলি; এক root মানে এক group।
  • chars = sorted(res[i] for i in idxs) — group-এর char-গুলো বর্ণানুক্রমে; এগুলোই smallest বিন্যাসের কাঁচামাল।
  • for i, c in zip(sorted(idxs), chars) — index গুলোও sort করে, ছোট index-এ ছোট char বসাই — এটাই lexicographic minimum।
  • return "".join(res) — সাজানো list থেকে চূড়ান্ত string।

17. Output walkthrough

প্রথম test-এ {0,3}→'b','d' আর {1,2}→'a','c' বসে "bacd"। দ্বিতীয়টায় [0,2] সব index এক group করে; "dcab" sort হয়ে "abcd"। তৃতীয়টায় তিন index এক group, "cba"→"abc"। no-pairs case-এ প্রতিটা index একা group, কিছুই বদলায় না — "abc"। শেষে print: সব test pass!।

18. Time complexity

O(n log n + P · α(n)) ≈ O(n log n + P) — P pair union (amortized near-constant), index bucket-এ ফেলা O(n), আর group-প্রতি sort মিলিয়ে মোট O(n log n)। sorting-ই dominating।

19. Space complexity

O(n) — parent + size array, groups dictionary, আর result list — সবই O(n)।

20. Common mistakes

  • group-এর char sort করে input-order index-এ বসানো (sorted index নয়) — তখন ছোট char ছোট index-এ না-ও পড়তে পারে; index-ও sort করতে হবে।
  • bucket করতে parent[i] ব্যবহার করা find(i)-এর বদলে — tree flat না হলে parent ≠ representative; classic DSU bug।
  • প্রতি group আলাদা sort না করে পুরো string sort করা — তখন আলাদা group-এর char মিশে যায়, যা swap-এ অনুমোদিত নয়।

21. Which basic problem this inherits from

ভিত্তি দুটো: এই tracker-এর grouping pattern (Pattern D) — swap relation = equivalence class; আর ../../02-arrays-and-strings/-এর sorting — group-এর ভেতরে smallest বিন্যাস পেতে sort। DFS দিয়েও group বের করা যায়; কিন্তু "কোন index এক সাথে নড়ে?" DSU-তে সবচেয়ে সরাসরি, বিশেষত pair অনেক হলে।

22. Similar harder problems

23. Pattern learned

Group then sort inside groups: যা একসাথে নাড়ানো যায় তাদের union করে group বানাও; প্রতি group-এর উপাদান sort করে group-এর sorted position-এ বসাও — সেটাই lexicographic/ordered optimum। "swap করা যায়" বা "interchangeable" শুনলে এই combo সরাসরি খাটে।

24. Final summary

ভবিষ্যতের আমাকে: "এই position-গুলো swap করে smallest বানাও" দেখলে swap-sequence খোঁজা ছাড়ো — কোন index-রা এক box (group) বের করো, প্রতি box-এ char sort করে sorted index-এ বসাও। Process নয়, structure ভাবো — এটাই এই grouping+sort pattern-এর মূল।

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