टीएल;डीआर

  • समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
  • दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ८.८: डुप्लिकेट अक्षर वाले स्ट्रिंग के हर अनोखे परमुटेशन की सूची। फ़्रीक्वेंसी मैप बनाओ, बचे काउंट से बैकट्रैक करो, सादे स्वैप वाले एन! विस्फोट से बचो।
  • जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

अलग-अलग अक्षरों के हर क्रम की सूची बनाना तुम जानते हो: अगला अक्षर चुनो, रीकर्स करो, वापस रखो। वही समस्या ८.७ है। जैसे ही स्ट्रिंग में दोहराव आते हैं ("aab", "mississippi"), सादा पेड़ एक ही स्ट्रिंग कई बार छापता है। समस्या ८.८ सिर्फ अनोखे परमुटेशन माँगती है, बिना विशाल सूची बनाकर बाद में छाने।

यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। मल्टीसेट परमुटेशन इंटरव्यू सवालों का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ८, रीकर्शन और डीपी, समस्या ८.८।

१. रोज़मर्रा की उपमा

स्क्रैबल टाइलें मुँह ऊपर रखी हैं: दो A और एक B। सब टाइलें घुमाकर कितने अलग शब्द बना सकते हो?

अगर दोनों A टाइलें अलग रंग की होतीं, उन्हें अदला-बदली कर अलग शब्द होने का नाटक कर सकते। वे अलग नहीं हैं। पाठक सिर्फ अक्षर देखता है। इसलिए:

  • सब अक्षर अनोखे हों: गिनती n!।
  • डुप्लिकेट हों: गिनती n! / (f1! · f2! · …) जहाँ fi बताता है कि अक्षर i कितनी बार आता है।

"aab" के लिए यह ३! / २! = ३ स्ट्रिंग: aab, aba, baa। छह नहीं।

एल्गोरिदम को सिर्फ ये तीन शाखाएँ उगानी चाहिए। छह उगाकर तीन फेंकना नहीं।

२. सादे शब्दों में समस्या

इनपुट: लंबाई n वाला स्ट्रिंग s। अक्षर दोहरा सकते हैं। केस और वर्णमाला इंटरव्यूअर तय करे; स्ट्रिंग को अक्षरों का मल्टीसेट मानो।

आउटपुट: वे सब अलग स्ट्रिंग जो s का हर अक्षर ठीक एक बार इस्तेमाल करें (मल्टीसेट के पूरे-लंबाई परमुटेशन)। सूची का क्रम मायने नहीं रखता, जब तक वे सॉर्टेड आउटपुट न माँगें।

उदाहरण:

इनपुट अनोखे परमुटेशन
"" एक खाली स्ट्रिंग (या खाली सूची: एक रिवाज चुनो और उसी पर टिके रहो)
"a" ["a"]
"ab" ["ab", "ba"]
"aab" ["aab", "aba", "baa"]
"aaa" ["aaa"]

कोड से पहले पूछो:

  • खाली इनपुट: [""] या []? यहाँ शिक्षण चुन: एक खाली नतीजा, ८.७ जैसा बेस केस।
  • केस सेंसिटिव? हाँ, जब तक न कहें (A ≠ a)।
  • सॉर्टेड आउटपुट? ज़रूरी नहीं। चाहें तो आखिर में सॉर्ट।
  • कॉलर का इनपुट म्यूटेट? नहीं। मैप और बिल्डर पर काम करो।

सबसेट के परमुटेशन नहीं माँगे (वह पावर सेट के करीब)। सिर्फ पूरी लंबाई।

३. पहले सोचो

"सब बनाओ फिर सेट में डालो" कमज़ोर क्यों है

८.७ वाला स्वैप रीकर्शन चलाकर हर स्ट्रिंग HashSet में डाल सकते हो। छोटे n पर सही। लागत फिर भी सर्च ट्री में मल्टीसेट के सभी क्रमों के अनुपात में रहती है, जो बहुत डुप्लिकेट पर अनोखी गिनती से कहीं बड़ी है। इंटरव्यूअर चाहते हैं कि डुप्लिकेट बनाओ ही मत, सेट में छुपाओ नहीं।

फ़्रीक्वेंसी मैप का विचार

गिनो कि हर अक्षर अभी कितनी बार उपलब्ध है:

"aab" → { a: 2, b: 1 }

आंशिक स्ट्रिंग के हर कदम पर:

१. हर अक्षर c जिसके लिए काउंट > 0 हो, अगला c चुनो। २. count[c] घटाओ, c जोड़ो, रीकर्स करो। ३. कॉल के बाद वापस: c हटाओ, count[c] बढ़ाओ।

दोनों a टाइलें मैप में एक ही कुंजी साझा करती हैं, इसलिए a से शुरू होने वाली एक शाखा है, दो नहीं। यही पूरा ट्रिक है।

रीकर्शन का आकार

prefix = ""
counts = {a:2, b:1}

  pick a → prefix "a", counts {a:1, b:1}
    pick a → "aa", {a:0, b:1}
      pick b → "aab"  (हो गया)
    pick b → "ab", {a:1, b:0}
      pick a → "aba"  (हो गया)
  pick b → prefix "b", counts {a:2, b:0}
    pick a → "ba", {a:1, b:0}
      pick a → "baa"  (हो गया)

तीन पत्ते। कोई डुप्लिकेट पत्ता नहीं।

८.७ से तुलना

८.७ बिना डुप ८.८ डुप के साथ
चुनाव का स्रोत बचे इंडेक्स / न इस्तेमाल अक्षर जिनका बचा काउंट > ०
ब्रांच फ़ैक्टर अलग न इस्तेमाल पोज़िशन अभी उपलब्ध अक्षर कुंजियाँ
नतीजे का आकार n! n! / ∏ fi!
अतिरिक्त संरचना यूज़्ड बूलियन ऐरे, या स्वैप Map या काउंट ऐरे

अगर हर अक्षर अनोखा हो, फ़्रीक्वेंसी तरीका फिर भी चलता है और n! नतीजे देता है। यह ८.७ का सख्त सामान्यीकरण है।

काउंट के लिए डेटा संरचना

  • आकार २६ का ऐरे अगर समस्या सिर्फ अंग्रेज़ी लोअरकेस हो। तेज़ और सादा।
  • HashMap<Character, Integer> सामान्य यूनिकोड / मिला-जुला केस के लिए। थोड़ा ज़्यादा कोड, जब वर्णमाला अज्ञात हो तो साफ़।

नीचे मुख्य समाधान में मैप है ताकि चुपचाप a-z न मान बैठे।

बिल्डर का चुनाव

मौजूदा प्रीफ़िक्स के लिए StringBuilder। रीकर्स से पहले अपेंड, लौटते समय setLength या deleteCharAt। हॉट पाथ में String जोड़ से बचो अगर बीच का कचरा मायने रखता हो; व्हाइटबोर्ड पर छोटे n के लिए दोनों ठीक।

४. जावा समाधान

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class PermutationsWithDups {

    public List<String> permutations(String s) {
        List<String> result = new ArrayList<>();
        if (s == null) {
            return result;
        }

        Map<Character, Integer> counts = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }

        backtrack(counts, new StringBuilder(), s.length(), result);
        return result;
    }

    private void backtrack(
            Map<Character, Integer> counts,
            StringBuilder path,
            int targetLen,
            List<String> result) {

        if (path.length() == targetLen) {
            result.add(path.toString());
            return;
        }

        // Iterate a snapshot of keys so we do not depend on map mutation order quirks.
        for (Character c : new ArrayList<>(counts.keySet())) {
            int remaining = counts.get(c);
            if (remaining <= 0) {
                continue;
            }

            counts.put(c, remaining - 1);
            path.append(c);

            backtrack(counts, path, targetLen, result);

            path.deleteCharAt(path.length() - 1);
            counts.put(c, remaining);
        }
    }
}

चलकर देखो: "aab"

१. काउंट बनाओ {a=2, b=1}। targetLen = 3। २. ऊपर पहला चुनाव a: पाथ "a", काउंट {a=1, b=1}। ३. अगला a: पाथ "aa", काउंट {a=0, b=1}। सिर्फ b बचा → "aab"। दर्ज करो। वापस लो। ४. अभी भी पाथ "a" के नीचे, अगला चुनाव b: पाथ "ab", फिर सिर्फ a → "aba"। दर्ज। वापस। ५. खाली पाथ पर लौटकर चुनाव b: पाथ "b", फिर दो a क्रम से मजबूर → सिर्फ "baa"। दर्ज। ६. खत्म। तीन स्ट्रिंग।

हर स्तर पर कुंजियाँ क्यों घुमाएँ

अक्षर तभी रखो जब काउंट धनात्मक हो। शून्य बची कुंजियाँ छोड़ दो। कुछ लोग शून्य कुंजी मैप से हटाकर अनडू पर वापस डालते हैं; चलता है, दबाव में गलती आसान। कुंजी छोड़कर remaining <= 0 जाँचना सुस्त और सुरक्षित है।

वैकल्पिक: तय वर्णमाला ऐरे

अगर इंटरव्यूअर सिर्फ लोअरकेस a-z बाँध दे:

int[] counts = new int[26];
for (int i = 0; i < s.length(); i++) {
    counts[s.charAt(i) - 'a']++;
}

// in backtrack:
for (int i = 0; i < 26; i++) {
    if (counts[i] == 0) {
        continue;
    }
    counts[i]--;
    path.append((char) ('a' + i));
    backtrack(counts, path, targetLen, result);
    path.deleteCharAt(path.length() - 1);
    counts[i]++;
}

वही कंट्रोल फ्लो। तेज़ कॉन्स्टेंट, संकरा इनपुट करार।

धुआँ परीक्षण

PermutationsWithDups p = new PermutationsWithDups();

assert p.permutations("").equals(List.of(""));
assert p.permutations("a").equals(List.of("a"));

List<String> ab = p.permutations("ab");
assert ab.size() == 2 && ab.contains("ab") && ab.contains("ba");

List<String> aab = p.permutations("aab");
assert aab.size() == 3;
assert aab.contains("aab") && aab.contains("aba") && aab.contains("baa");

assert p.permutations("aaa").equals(List.of("aaa"));

५. जटिलता तालिका

n स्ट्रिंग की लंबाई हो। k अलग अक्षरों की संख्या हो। U अनोखे परमुटेशन की संख्या हो, U = n! / ∏ fi!।

टुकड़ा लागत नोट
काउंट बनाना ओ(एन) समय, ओ(के) स्थान एक पास
सर्च ट्री आकार लगभग Θ(यू · एन) नोड हर अनोखा नतीजा लंबाई एन का पाथ; भीतरी नोड प्रीफ़िक्स साझा करते हैं
प्रति नोड काम कुंजियाँ स्कैन करने पर ओ(के) (मैप) या २६ पर ऐरे से औसत ओ(१) कॉन्स्टेंट पर हावी
आउटपुट आकार ओ(यू · एन) हर स्ट्रिंग लिखनी पड़ती है
अतिरिक्त स्टैक ओ(एन) रीकर्शन गहराई पाथ लंबाई
कुल समय ओ(यू · एन · के) शैली बहुत डुप्लिकेट पर ओ(एन! · एन) से बेहतर
कुल स्थान ओ(एन + के + यू · एन) स्टैक + मैप + आउटपुट

ज़ोर से बोलो: जो अनोखे स्ट्रिंग लौटाते हो उनका भुगतान तो होगा। स्वैप+सेट वाले तरीके से रद्द डुप्लिकेट क्रमों का भुगतान नहीं।

सबसे बुरा: सब अक्षर अलग, U = n!, ८.७ जैसा क्रम। सबसे अच्छा: सब अक्षर एक जैसे, U = 1, और पेड़ एक ही रास्ता।

६. किनारे के मामले और आम गलतियाँ

इंटरव्यूअर ये छूते हैं:

  • सब एक जैसे ("aaaa") → ठीक एक नतीजा। मैप में एक कुंजी; हर कदम पर एक ही चुनाव।
  • सब अलग ("abcd") → २४ नतीजे। फ़्रीक्वेंसी कोड फिर भी चले।
  • खाली स्ट्रिंग → एक खाली परमुटेशन (अगर वही बेस केस हो)।
  • नल → खाली सूची; s.length() पर एनपीई मत दो।
  • एक अक्षर → उस एक-अक्षर स्ट्रिंग की सूची।
  • एक अक्षर बहुत, दूसरा कम ("aaab") → ४ अनोखे नतीजे (aaab, aaba, abaa, baaa)। सूत्र: ४! / ३! = ४।

आम गलतियाँ:

१. सभी स्वैप परमुटेशन बनाकर सेट में डालना। डेमो पर चलता है, शाखाएँ बर्बाद। गिनती सूत्र बोलो, स्रोत पर काटो। २. सॉर्ट के बाद सिर्फ "पिछले जैसा" छोड़ना, पर सॉर्ट या स्किप गलत। यूनीक सबसेट वाला सॉर्ट-एंड-स्किप परमुटेशन पर भी चल सकता है अगर यूज़्ड इंडेक्स सावधानी से मार्क हों। मल्टीसेट परमुटेशन के लिए फ़्रीक्वेंसी मैप साफ़ है। ३. लौटते समय काउंट वापस न लगाना। बहन शाखा गलत स्टॉक देखती है। ४. मैप की कुंजी सेट म्यूटेट करते हुए इटरेट बिना स्नैपशॉट। कुंजियाँ कॉपी करो या ऐरे लो। ५. आधी लंबाई वाले स्ट्रिंग लौटाना। रोक तभी जब path.length() == n। ६. बिना पूछे "Ab" पर केस-फोल्ड। बराबरता फिर से परिभाषित न हो तो सटीक अक्षर रखो।

७. दोस्त को समझाओ सार

डुप वाले परमुटेशन, इंटरव्यू वर्शन:

१. गिनो हर अक्षर अभी कितने बचे। २. जवाब एक-एक अक्षर से बनाओ। ३. हर कदम पर हर वह अक्षर आज़माओ जिसका बचा काउंट धनात्मक हो। कभी अलग से मत पूछो "कौन सी भौतिक a टाइल"। ४. घटाओ, रीकर्स, वापस लगाओ। ५. जब पाथ की लंबाई n छुए, स्ट्रिंग दर्ज करो। ६. नतीजे का आकार n! / ∏ fi! है, n! नहीं। ७. ८.७ जैसा ही ढाँचा; मैप यूज़्ड-इंडेक्स सेट की जगह लेता है और डुप्लिकेट अपने आप सिकुड़ जाते हैं।

अगर "aab" के तीन-पत्ते वाले पेड़ खींच सको और बता सको कि दो एक जैसी a टाइलें एक शाखा क्यों साझा करती हैं, समस्या ८.८ तुम्हारी है। आगे संतुलित कोष्ठक जनन उसी तरह "अगला वैध चिह्न चुनो" बैकट्रैक इस्तेमाल करता है।

सीरीज़