Problem link ও উৎস
- **Original source:** Classic competitive-programming exercise (distinct permutations of a string)
- **Platform:** CSES —
(task name: Creating Strings)
- **Topic:** recursion / backtracking (permutations with duplicates)
- **Difficulty:** Medium
- **Pattern:** permutations with duplicates — sorted করে নাও, প্রতি level-এ একই অক্ষর একবারই
- **Basic idea inherited from:** CP-গতিতে Permutations II
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা string দেওয়া আছে (অক্ষরে duplicate থাকতে পারে)। তোমার কাজ: ওই অক্ষরগুলো দিয়ে গড়া **সব আলাদা (distinct) সাজানো** বের করা — মানে সব unique permutation, alphabetical (sorted) ক্রমে। CSES-এ আগে মোট কয়টা তা ছাপাতে হয়, তারপর প্রতিটা string আলাদা লাইনে। মূল কথা — duplicate অক্ষর থাকলেও একই string দুবার দেওয়া যাবে না।
```text
s = "aabac" -> অনেকগুলো distinct permutation
s = "aa" -> শুধু "aa" (count 1)
s = "ab" -> "ab", "ba" (count 2)
```
### Input ও output {#8-example-input-and-output}
```text
Input : "ab" -> Output: count 2; "ab", "ba"
Input : "aab" -> Output: count 3; "aab", "aba", "baa"
Edge case 1 (এক অক্ষর): "a" -> count 1; "a"
Edge case 2 (সব সমান): "aaa" -> count 1; "aaa"
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
হাতে কয়েকটা Scrabble টাইল, কয়েকটা একই অক্ষরের (যেমন দুটো 'A')। তুমি সব রকম শব্দ সাজাতে চাও, কিন্তু দুটো 'A' দেখতে এক — ওদের জায়গা বদল করলে "নতুন" শব্দ হয় না। তাই প্রতিটা position-এ এক ধরনের টাইল একবারই বসাও; তাহলে কোনো সাজ দুবার গোনা হয় না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি হলো **Permutations II — CP-গতিতে**। সাধারণ Permutations-এ প্রতি level-এ যে অক্ষর এখনো `used` হয়নি তাকে বসাই; কিন্তু duplicate অক্ষর থাকলে একই string বারবার আসে। সমাধান একই sort-and-skip চাল: আগে string sorted করে নিই, তারপর প্রতি level-এ একই মানের পরপর অক্ষরের মধ্যে শুধু **প্রথমটা** ব্যবহার করি (আগেরটা যদি এই branch-এ এখনো বসানো না হয়)। তাই duplicate permutation গাছেই জন্মায় না।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো math হলো **multiset permutation count**: `n`টা অক্ষর, একটা অক্ষর `c` যদি `k_c` বার থাকে, তাহলে distinct permutation = `n! / (k_a! · k_b! · ...)`। ভাগগুলো একই অক্ষরের নিজেদের মধ্যে অদলবদল বাদ দেয়। skip-নিয়মটা ঠিক এই অতিরিক্ত গণনাটাই কেটে দেয় — প্রতিটা distinct multiset-permutation ঠিক একবার করে গড়ে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
লাগে **sorted `chars`** (string sort করে list), একটা **boolean `used` array** (কোন index বসানো), একটা **list `path`** (বর্তমান permutation গড়তে), একটা **list `out`** (সব result জমাতে), আর recursion-এর জন্য **call stack**। sort + `used` + skip-condition একসাথে duplicate ঠেকায়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
string sorted রাখায় একই অক্ষর পরপর বসে, তাই duplicate skip শর্তটা (`chars[i] == chars[i-1]`) শুধু পাশের index দেখেই কাজ করে — O(1)। `used` array O(1)-তে বলে দেয় index-টা এই path-এ বসানো কিনা। আর যেহেতু আমরা index 0→n ক্রমে চেষ্টা করি ও skip করি, output **আপনিই sorted** আসে — আলাদা sort লাগে না, CSES-এর alphabetical দাবি এমনিই মেটে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: সাধারণ permutation generator চালাও (sort বা skip ছাড়া) — সব `n!` সাজ গড়ো — তারপর সেগুলো একটা `set`-এ ফেলে duplicate বাদ দাও, শেষে sort করো।
```text
all_perms = generate_all_permutations(chars) # n! টা, duplicate সহ
distinct = sorted(set(all_perms))
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই version সবসময় পুরো `n!` সাজ গড়ে — অথচ অনেক অক্ষর সমান হলে distinct সংখ্যা `n!`-এর চেয়ে অনেক কম (`n!/∏k!`)। যেমন `"aaaa"`-তে `n! = 24` সাজ গড়ে শেষে মাত্র 1টা রাখে — 23টাই অপচয়, তার ওপর `set`-এ ঢোকানোর hashing খরচ। sort-and-skip version হিসেব-মতো ঠিক distinct সংখ্যক branch-ই খোলে; অপচয় শূন্য, আর output এমনিতেই sorted।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **duplicate এড়াতে "সমান অক্ষরের মধ্যে একটা নির্দিষ্ট ক্রম" চাপিয়ে দাও** — পরপর একই অক্ষরের মধ্যে আগেরটা আগে বসবে। sorted অবস্থায় শর্তটা দাঁড়ায়: `chars[i] == chars[i-1]` আর `i-1` এখনো এই branch-এ unused হলে `i` skip। এতে প্রতিটা distinct সাজ ঠিক একবার, প্রথম-আসা ক্রমেই গড়ে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`go(path)`: base case `len(path) == n` হলে `"".join(path)` record। নাহলে `i` 0→n: `used[i]` হলে skip; `i>0` ও `chars[i]==chars[i-1]` ও `not used[i-1]` হলে skip (duplicate গেট); নাহলে `used[i]=True`, append, recurse, তারপর pop + `used[i]=False`। sorted ক্রম + এই গেট = distinct, sorted output।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব permutation গড়ে duplicate ফেলে দেব" নয় — বরং "একই অক্ষরকে একই position-এ একবারই বসতে দেব।" duplicate-কে শেষে filter না করে গড়ার সময়ই ঠেকাও। এক লাইনের skip-শর্ত (`chars[i]==chars[i-1] and not used[i-1]`) পুরো অতিরিক্ত গণনাটা কেটে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
sorted `chars`; প্রতি level-এ unused index বসাও, কিন্তু duplicate অক্ষর হলে শুধু প্রথমটা। `s="aab"` → `chars=[a,a,b]`:
```text
go(path=[])
a(idx0) / a(idx1: skip, আগের a unused) | b(idx2)
go([a]) go([b])
a(idx1)/ b(idx2)\ a(idx0)/ a(idx1: skip)
go([a,a]) go([a,b]) go([b,a])
b(idx2)| a(idx0)| a(idx1)|
[a,a,b] [a,b,a] [b,a,a]
distinct = 3 = 3!/2!; "aab","aba","baa" — sorted ক্রমেই বেরোয়।
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`creating_strings("aab")`, `chars=[a,a,b]`, `go(path)`:
1. `go([])`: `i=0` `a` বসাও (`used=[T,F,F]`) → `go([a])`।
2. `go([a])`: `i=1` `a` বসাও → `go([a,a])`; `i=2` `b` → `go([a,a,b])`: record `"aab"`; পিছিয়ে।
3. `go([a])`: `i=2` `b` বসাও → `go([a,b])`; `i=0` `a` → record `"aba"`।
4. `go([])`: `i=1` `a` — skip (`chars[1]==chars[0]` আর `used[0]` False)। `i=2` `b` → `go([b])` → `a` → `a` → record `"baa"`।
5. out = `["aab", "aba", "baa"]` — 3টা, sorted।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def creating_strings(s):
chars = sorted(s) # sort -> duplicate পাশাপাশি, output sorted
n = len(chars)
used = [False] * n
out = []
path = []
def go():
if len(path) == n: # base case: সব অক্ষর বসানো
out.append("".join(path)) # string snapshot
return
for i in range(n):
if used[i]:
continue # এই index অলরেডি বসানো
if i > 0 and chars[i] == chars[i - 1] and not used[i - 1]:
continue # duplicate গেট: সমান অক্ষরের প্রথমটাই কেবল
used[i] = True # CHOOSE
path.append(chars[i])
go() # EXPLORE
path.pop() # UN-CHOOSE
used[i] = False
go()
return out
# ---- tests (output sorted ও distinct, তাই সরাসরি তুলনা) ----
assert creating_strings("a") == ["a"]
assert creating_strings("ab") == ["ab", "ba"]
assert creating_strings("aab") == ["aab", "aba", "baa"]
assert creating_strings("aaa") == ["aaa"] # সব সমান -> 1টা
assert len(creating_strings("aabb")) == 6 # 4!/(2!2!)
assert creating_strings("aabb") == sorted(creating_strings("aabb")) # alphabetical
assert len(creating_strings("abc")) == 6 # 3! (সব আলাদা)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `chars = sorted(s)` — sort করায় একই অক্ষর পাশাপাশি বসে; ফলে duplicate-check পাশের index দেখেই হয়, আর output sorted।
- `used = [False]*n` — কোন index এই path-এ বসানো তা track।
- `if len(path) == n:` — base case: পূর্ণ একটা permutation।
- `if used[i]: continue` — বসানো index আবার নেওয়া যাবে না।
- `if chars[i]==chars[i-1] and not used[i-1]: continue` — duplicate গেট: পরপর সমান অক্ষরের মধ্যে আগেরটা না বসিয়ে পরেরটা নিলে একই string পুনরাবৃত্তি হতো।
- `used[i]=True; path.append; go(); path.pop(); used[i]=False` — choose → explore → un-choose।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`creating_strings("aab")`: `chars=[a,a,b]`; প্রথম level-এ index 0-এর `a` খোলে, index 1-এর `a` skip (duplicate গেট), index 2-এর `b` খোলে — তাই `"aab"`, `"aba"`, `"baa"` ঠিক একবার করে, alphabetical ক্রমে। `"aaa"`-তে সব level-এ একটাই branch → 1টা। `"aabb"`-তে `4!/(2!2!)=6`, আর `sorted()`-এর সাথে মিলিয়ে দেখাই output আগে থেকেই sorted। সব মিলে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n · n!/∏k!)** — distinct permutation সংখ্যা `n!/∏(kᵢ!)`, প্রতিটা গড়তে ও join করতে O(n)। duplicate skip থাকায় শুধু distinct branch-ই খোলে, তাই কোনো অপচয় নেই (brute force-এর `n!`-এর তুলনায় অনেক কম)।
### অতিরিক্ত জায়গা {#19-space-complexity}
Output বাদ দিলে **O(n)** — `path`, `used`, ও call stack-এর গভীরতা n পর্যন্ত। Output ধরলে সব distinct permutation-এর মোট আকার।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- string sort না করা — তখন duplicate অক্ষর পাশাপাশি থাকে না, skip-শর্ত কাজ করে না, ফলে duplicate permutation বেরোয়।
- skip-শর্তে `not used[i-1]`-এর বদলে `used[i-1]` লেখা — distinct সাজ বাদ পড়ে যায় (under-count)।
- `out.append(path)` snapshot ছাড়া — সব entry একই live list-এর reference।
- count আলাদা করে গুনতে গিয়ে result-সংখ্যার সাথে অমিল — `len(out)`-ই count।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Permutations II (এই tracker-এর #14) — সেই sort-and-skip চাল হুবহু, এখানে অক্ষরের ওপর। [../patterns.md](../patterns.md)-এর permutation pattern + duplicate-skip গেট দেখো। CP-প্ল্যাটফর্মে (CSES) একই idea, শুধু আগে count ছাপানো + alphabetical output-এর দাবি — যা sorted-ক্রমে generate করায় এমনিতেই মেটে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Permutations II (LeetCode রূপ) —