018 — Creating Strings¶

Problem link ও উৎস

Original source: Classic competitive-programming exercise (distinct permutations of a string)
Platform: CSES — https://cses.fi/problemset/task/1622/ (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

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

একটা string দেওয়া আছে (অক্ষরে duplicate থাকতে পারে)। তোমার কাজ: ওই অক্ষরগুলো দিয়ে গড়া সব আলাদা (distinct) সাজানো বের করা — মানে সব unique permutation, alphabetical (sorted) ক্রমে। CSES-এ আগে মোট কয়টা তা ছাপাতে হয়, তারপর প্রতিটা string আলাদা লাইনে। মূল কথা — duplicate অক্ষর থাকলেও একই string দুবার দেওয়া যাবে না।

উদাহরণ

s = "aabac"  -> অনেকগুলো distinct permutation
s = "aa"     -> শুধু "aa" (count 1)
s = "ab"     -> "ab", "ba" (count 2)

Input ও output¶

উদাহরণ

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"

চেনা উদাহরণে বোঝা¶

হাতে কয়েকটা Scrabble টাইল, কয়েকটা একই অক্ষরের (যেমন দুটো 'A')। তুমি সব রকম শব্দ সাজাতে চাও, কিন্তু দুটো 'A' দেখতে এক — ওদের জায়গা বদল করলে "নতুন" শব্দ হয় না। তাই প্রতিটা position-এ এক ধরনের টাইল একবারই বসাও; তাহলে কোনো সাজ দুবার গোনা হয় না।

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

ভিত্তি হলো Permutations II — CP-গতিতে। সাধারণ Permutations-এ প্রতি level-এ যে অক্ষর এখনো used হয়নি তাকে বসাই; কিন্তু duplicate অক্ষর থাকলে একই string বারবার আসে। সমাধান একই sort-and-skip চাল: আগে string sorted করে নিই, তারপর প্রতি level-এ একই মানের পরপর অক্ষরের মধ্যে শুধু প্রথমটা ব্যবহার করি (আগেরটা যদি এই branch-এ এখনো বসানো না হয়)। তাই duplicate permutation গাছেই জন্মায় না।

ভেতরের যুক্তি¶

লুকানো math হলো multiset permutation count: nটা অক্ষর, একটা অক্ষর c যদি k_c বার থাকে, তাহলে distinct permutation = n! / (k_a! · k_b! · ...)। ভাগগুলো একই অক্ষরের নিজেদের মধ্যে অদলবদল বাদ দেয়। skip-নিয়মটা ঠিক এই অতিরিক্ত গণনাটাই কেটে দেয় — প্রতিটা distinct multiset-permutation ঠিক একবার করে গড়ে।

কী দিয়ে তথ্য রাখব¶

লাগে sorted chars (string sort করে list), একটা boolean used array (কোন index বসানো), একটা list path (বর্তমান permutation গড়তে), একটা list out (সব result জমাতে), আর recursion-এর জন্য call stack। sort + used + skip-condition একসাথে duplicate ঠেকায়।

এটি কেন উপযুক্ত¶

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 দাবি এমনিই মেটে।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা: সাধারণ permutation generator চালাও (sort বা skip ছাড়া) — সব n! সাজ গড়ো — তারপর সেগুলো একটা set-এ ফেলে duplicate বাদ দাও, শেষে sort করো।

উদাহরণ

all_perms = generate_all_permutations(chars)   # n! টা, duplicate সহ
distinct = sorted(set(all_perms))

কোথায় বেশি কাজ হচ্ছে¶

এই version সবসময় পুরো n! সাজ গড়ে — অথচ অনেক অক্ষর সমান হলে distinct সংখ্যা n!-এর চেয়ে অনেক কম (n!/∏k!)। যেমন "aaaa"-তে n! = 24 সাজ গড়ে শেষে মাত্র 1টা রাখে — 23টাই অপচয়, তার ওপর set-এ ঢোকানোর hashing খরচ। sort-and-skip version হিসেব-মতো ঠিক distinct সংখ্যক branch-ই খোলে; অপচয় শূন্য, আর output এমনিতেই sorted।

যে বিষয়টি খেয়াল করতে হবে¶

মূল observation: duplicate এড়াতে "সমান অক্ষরের মধ্যে একটা নির্দিষ্ট ক্রম" চাপিয়ে দাও — পরপর একই অক্ষরের মধ্যে আগেরটা আগে বসবে। sorted অবস্থায় শর্তটা দাঁড়ায়: chars[i] == chars[i-1] আর i-1 এখনো এই branch-এ unused হলে i skip। এতে প্রতিটা distinct সাজ ঠিক একবার, প্রথম-আসা ক্রমেই গড়ে।

আরও কম কাজে সমাধান¶

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।

ভাবনার পরিবর্তন¶

মোচড়: "সব permutation গড়ে duplicate ফেলে দেব" নয় — বরং "একই অক্ষরকে একই position-এ একবারই বসতে দেব।" duplicate-কে শেষে filter না করে গড়ার সময়ই ঠেকাও। এক লাইনের skip-শর্ত (chars[i]==chars[i-1] and not used[i-1]) পুরো অতিরিক্ত গণনাটা কেটে দেয়।

ছবিতে বোঝা¶

sorted chars; প্রতি level-এ unused index বসাও, কিন্তু duplicate অক্ষর হলে শুধু প্রথমটা। s="aab" → chars=[a,a,b]:

উদাহরণ

                        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-এ ধাপে ধাপে¶

creating_strings("aab"), chars=[a,a,b], go(path):

go([]): i=0 a বসাও (used=[T,F,F]) → go([a])।
go([a]): i=1 a বসাও → go([a,a]); i=2 b → go([a,a,b]): record "aab"; পিছিয়ে।
go([a]): i=2 b বসাও → go([a,b]); i=0 a → record "aba"।
go([]): i=1 a — skip (chars[1]==chars[0] আর used[0] False)। i=2 b → go([b]) → a → a → record "baa"।
out = ["aab", "aba", "baa"] — 3টা, sorted।

কোড ও ব্যাখ্যা¶

Python¶

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!")

কোডের প্রতিটি অংশ¶

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 মিলিয়ে দেখা¶

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!।

খরচ ও সাধারণ ভুল¶

সময়¶

O(n · n!/∏k!) — distinct permutation সংখ্যা n!/∏(kᵢ!), প্রতিটা গড়তে ও join করতে O(n)। duplicate skip থাকায় শুধু distinct branch-ই খোলে, তাই কোনো অপচয় নেই (brute force-এর n!-এর তুলনায় অনেক কম)।

অতিরিক্ত জায়গা¶

Output বাদ দিলে O(n) — path, used, ও call stack-এর গভীরতা n পর্যন্ত। Output ধরলে সব distinct permutation-এর মোট আকার।

যে ভুলগুলো এড়াতে হবে¶

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।

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

ভিত্তি: Permutations II (এই tracker-এর #14) — সেই sort-and-skip চাল হুবহু, এখানে অক্ষরের ওপর। ../patterns.md-এর permutation pattern + duplicate-skip গেট দেখো। CP-প্ল্যাটফর্মে (CSES) একই idea, শুধু আগে count ছাপানো + alphabetical output-এর দাবি — যা sorted-ক্রমে generate করায় এমনিতেই মেটে।

পরের অনুশীলন¶

Permutations II (LeetCode রূপ) — https://leetcode.com/problems/permutations-ii/ (এই tracker-এর #14)
Permutations (duplicate নেই) — https://leetcode.com/problems/permutations/ (#9)
Next Permutation (ক্রমিক সাজ) — https://leetcode.com/problems/next-permutation/

কৌশলটি মনে রাখুন¶

Permutations with duplicates (sort-and-skip): আগে sort করো, প্রতি level-এ unused index বসাও, কিন্তু পরপর সমান অক্ষরের মধ্যে আগেরটা unused থাকলে পরেরটা skip করো — duplicate গাছেই জন্মায় না, আর output আপনিই alphabetical।

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে: "Creating Strings = sorted chars + used array; প্রতি level-এ chars[i]==chars[i-1] and not used[i-1] হলে skip; base case len(path)==n।" যখনই 'duplicate সহ সব distinct সাজ, sorted-এ' শুনবে — এই sort-and-skip permutation skeleton মনে করবে; duplicate শেষে filter নয়, গড়ার সময়ই ঠেকাও।

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