Skip to content

018 — Creating Strings

Source

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

1. Problem in simple words

একটা 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)

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

6. Real-life analogy

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

7. Visual explanation

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 ক্রমেই বেরোয়।

8. Example input and 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"

9. Brute force thinking

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

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]) পুরো অতিরিক্ত গণনাটা কেটে দেয়।

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।

15. Python solution

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।

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

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।

21. Which basic problem this inherits from

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

22. Similar harder problems

23. Pattern learned

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

24. Final summary

ভবিষ্যতের আমাকে: "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।