क्या यूनिक है: स्ट्रिंग के सभी अक्षर अलग हैं या नहीं (जावा)

टीएल;डीआर

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

आप एक छोटी पार्टी में मेहमानों के नाम चेक कर रहे हैं। हर व्यक्ति सिर्फ एक बार दाखिल हो। अगर कोई पहले ही सूची में है, तो रोक दो। “क्या यूनिक है” का पूरा विचार यही है: अक्षरों पर चलो और पहली पुनरावृत्ति पकड़ो।

यह पोस्ट जावा में बिल्कुल शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू के क्लासिक ऐरे-स्ट्रिंग वार्मअप जैसी समस्या, किसी किताब की नकल नहीं। सीटीसीआई जावा श्रृंखला का हिस्सा।

---

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

एक स्टिकर का रोल सोचो। हर स्टिकर पर एक अक्षर है। तुम उन्हें एक-एक करके मेज़ पर चिपकाते हो।

• अगर ऐसा अक्षर निकला जो पहले नहीं देखा, तो चिपकाओ और आगे बढ़ो।
• अगर ऐसा अक्षर निकला जो मेज़ पर पहले से है, तो रोल यूनिक नहीं।

स्ट्रिंग वही रोल है। काम सिर्फ इतना: हाँ (सब अलग) या नहीं (कोई अक्षर दो बार)।

---

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

इनपुट: एक स्ट्रिंग s (उदाहरण "abc", "hello", या "")।

आउटपुट: true अगर हर अक्षर ज़्यादा से ज़्यादा एक बार आए, वरना false।

उदाहरण:

इनपुट	परिणाम	क्यों
"abc"	true	अ, ब, स हर एक एक बार
"hello"	false	l दो बार
"Aa"	true अगर केस मायने रखे (डिफ़ॉल्ट)	जावा में A और a अलग
""	true	खाली में कोई डुप्लिकेट नहीं
"a"	true	एक ही अक्षर

कोड से पहले पूछो (इंटरव्यू में ज़ोर से बोलो):

• वर्णमाला ऐस्की (० से १२७), विस्तारित ऐस्की (० से २५५), या पूरा यूनिकोड?
• केस मायने रखता है? ("AbA" केस अनदेखा करने पर दो A)
• खाली या नल हो सकती है?
• पहले डुप्लिकेट का इंडेक्स चाहिए, या सिर्फ हाँ/नहीं?

इस लेख में मानते हैं: जावा का नॉन-नल String, केस सेंसिटिव, और अक्सर पहले ऐस्की पर ऑप्टिमाइज़ क्योंकि इंटरव्यू उसी रास्ते को पसंद करते हैं।

---

३. पहले सोचो (ब्रूट फोर्स, फिर बेहतर)

ब्रूट फोर्स

हर इंडेक्स i के लिए आगे के सारे अक्षर देखो और पूछो: क्या s.charAt(j) बराबर है s.charAt(i) के?

• समय: लंबाई न के लिए लगभग ओ(न²) तुलनाएँ।
• जगह: अतिरिक्त मेमोरी ओ(१)।
• छोटी स्ट्रिंग पर ठीक। न बढ़े तो दर्द।

boolean isUniqueBrute(String s) {
    int n = s.length();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) {
                return false;
            }
        }
    }
    return true;
}

बेहतर विचार: जो देखा, याद रखो

हर अक्षर के लिए पूरी स्ट्रिंग दोबारा स्कैन करने की ज़रूरत नहीं। देखे गए अक्षरों का सेट रखो। जो पहले से सेट में है, आते ही false। एक ही पास।

स्टिकर वाली मेज़ वाला ही दिमागी कदम।

ऐस्की के लिए और कसकर: तय आकार के झंडे

अगर सिर्फ १२८ (या २५६) कोड संभव हैं, बढ़ते सेट की ज़रूरत नहीं। उसी आकार का बूलियन ऐरे। अक्षर के कोड से इंडेक्स। समय ओ(न), जगह वर्णमाला के सापेक्ष ओ(१) (न के सापेक्ष नहीं)।

तेज़ जीत: अगर लंबाई वर्णमाला से बड़ी है, तो ज़रूर डुप्लिकेट है (कबूतरखाना सिद्धांत)। तुरंत false।

---

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

(अ) बूलियन ऐरे (ऐस्की)

क्लासिक इंटरव्यू जवाब, जब इंटरव्यूअर “ऐस्की मान लो” स्वीकार करे।

boolean isUniqueAscii(String s) {
    // कोड से ज़्यादा अक्षर? डुप्लिकेट तय।
    if (s.length() > 128) {
        return false;
    }

    boolean[] seen = new boolean[128];
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c >= 128) {
            // मानी गई वर्णमाला के बाहर; संभालो या अस्वीकार।
            throw new IllegalArgumentException("Non-ASCII char");
        }
        if (seen[c]) {
            return false; // यह कोड पहले इस्तेमाल हो चुका
        }
        seen[c] = true;
    }
    return true;
}

बिट वाला संस्करण (वही विचार, सिर्फ अ से जेड छोटे अक्षरों के लिए कम जगह):

अगर स्ट्रिंग सिर्फ अंग्रेज़ी छोटे अक्षर (a से z) है, २६ झंडे एक int (३२ बिट) में समा जाते हैं। बिट k मतलब “कोड a + k वाला अक्षर पहले आ चुका”।

boolean isUniqueLowercaseBits(String s) {
    if (s.length() > 26) {
        return false;
    }
    int mask = 0;
    for (int i = 0; i < s.length(); i++) {
        int bit = s.charAt(i) - 'a';
        if (bit < 0 || bit > 25) {
            throw new IllegalArgumentException("Expected a-z only");
        }
        int flag = 1 << bit;
        if ((mask & flag) != 0) {
            return false;
        }
        mask |= flag;
    }
    return true;
}

बिट वैकल्पिक सजावट है। पहले बूलियन ऐरे सीखो। बिट तभी जब वर्णमाला छोटी हो और जगह पर सवाल हो।

(ब) हैशसेट (सामान्य अक्षरों के लिए)

import java.util.HashSet;
import java.util.Set;

boolean isUniqueHashSet(String s) {
    Set<Character> seen = new HashSet<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (!seen.add(c)) {
            // पहले से मौजूद होने पर add false लौटाता है
            return false;
        }
    }
    return true;
}

यूनिकोड बिना १२८ स्लॉट वाले ऐरे के संभलता है। जगह अलग-अलग अक्षरों के साथ बढ़ती है (अधिकतम न)। साफ़, समझाने में आसान, खुली वर्णमाला पर प्रोडक्शन में सुरक्षित डिफ़ॉल्ट।

(स) सॉर्ट करके पड़ोसी देखो (वैकल्पिक)

अगर अक्षरों की कॉपी फिर से व्यवस्थित कर सकते हो, तो सॉर्ट करो। कोई भी डुप्लिकेट बगल में आ जाता है।

import java.util.Arrays;

boolean isUniqueSort(String s) {
    char[] chars = s.toCharArray();
    Arrays.sort(chars);
    for (int i = 1; i < chars.length; i++) {
        if (chars[i] == chars[i - 1]) {
            return false;
        }
    }
    return true;
}

• समय: सॉर्ट से ओ(न लॉग न)।
• जगह: char[] कॉपी के लिए ओ(न) (जावा String अपरिवर्तनीय)।
• तब अच्छा जब हैश संरचना न मिले लेकिन सॉर्ट मिले।

---

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

तरीका	समय	अतिरिक्त जगह	नोट
नेस्टेड लूप	ओ(न²)	ओ(१)	कोई अतिरिक्त संरचना नहीं
बूलियन ऐरे (ऐस्की)	ओ(न)	ओ(१) वर्णमाला	१२८ या २५६ कोड मानो
बिट मास्क (अ-ज़ेड छोटे)	ओ(न)	ओ(१)	सिर्फ अंग्रेज़ी छोटे अक्षर
हैशसेट	औसत ओ(न)	ओ(क)	क = अलग अक्षर
सॉर्ट + स्कैन	ओ(न लॉग न)	ओ(न)	कॉपी फिर सॉर्ट

वर्णमाला तय और छोटी हो तो बूलियन ऐरे। ऐस्की न मान सको तो हैशसेट। हैश मना हो तो ही सॉर्ट।

---

६. किनारे के मामले

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

• खाली स्ट्रिंग → अक्सर true (बराबर जोड़ा ही नहीं)।
• एक अक्षर → true।
• सब एक जैसे ("aaaa") → false।
• लंबाई वर्णमाला से बड़ी → तय वर्णमाला पर तुरंत false।
• नल → तय करो: अपवाद फेंको, या false। चुपचाप क्रैश मत करो।
• स्पेस और विराम → ये भी अक्षर गिने जाते हैं।
• यूनिकोड / सरोगेट → char यूटीएफ-१६ है। इमोजी दो char इकाई ले सकता है। सख्त कोड पॉइंट के लिए codePoints() से चलो।
• केस → "God" बनाम "god": केस सेंसिटिव हो तो अलग।

नल-सुरक्षित छोटा आवरण:

boolean isUniqueSafe(String s) {
    if (s == null) {
        throw new IllegalArgumentException("string is null");
    }
    return isUniqueHashSet(s);
}

---

७. दोस्त को समझाने वाला सार

“क्या यूनिक है” पूछता है: क्या यह स्ट्रिंग कोई अक्षर दोबारा इस्तेमाल करती है?

१. ब्रूट फोर्स हर जोड़े की तुलना करता है। धीमा लेकिन सही।
२. जो देखा याद रखो: सेट (या तय वर्णमाला पर बूलियन झंडे)।
३. हर अक्षर पर, अगर पहले देखा तो false; वरना चिह्नित करो।
४. स्ट्रिंग वर्णमाला से लंबी हो तो डुप्लिकेट तय।
५. सॉर्ट बैकअप है: कॉपी करो, सॉर्ट करो, पड़ोसी चेक करो।

तीस सेकंड में इतना बोल सको और हैशसेट या बूलियन ऐरे बिना अटक लिख सको, तो समस्या १.१ तुम्हारी है।

श्रृंखला में आगे: परमुटेशन जाँच (दो स्ट्रिंग एक-दूसरे की पुनर्व्यवस्था हैं?)।