सीटीसीआई १.४ पैलिंड्रोम परम्यूटेशन जावा में: विषम गिनो, फेरबदल नहीं

टीएल;डीआर

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

पैलिंड्रोम बाएं से दाएं और दाएं से बाएं एक जैसा पढ़ा जाता है: kayak, level, और अगर स्पेस छोड़ दें तो a man a plan a canal panama। परम्यूटेशन उसी अक्षर-समूह का कोई भी फेरबदल है। यह समस्या शांत सवाल पूछती है: क्या इस स्ट्रिंग के किसी फेरबदल से पैलिंड्रोम बन सकता है? वह फेरबदल बनाना जरूरी नहीं। बस यह जानना है कि संभव है या नहीं।

यह क्रैकिंग द कोडिंग इंटरव्यू शैली सेट का समस्या १.४ है (ऐरे और स्ट्रिंग)। लेख मूल शिक्षण है, किसी किताब के हल की नकल नहीं।

---

रोजमर्रा की तस्वीर

मेज पर अक्षर की टाइलें सोचो। तुम उन्हें एक शब्द में लाइन करना चाहते हो जो दोनों सिरों से एक जैसा दिखे।

जोड़े मिलते-जुलते सीटों पर बैठते हैं: बाईं तरफ एक a के लिए दाईं तरफ और एक a चाहिए। अगर कोई अक्षर विषम बार आए, एक टाइल बच जाती है। वह बचट बीच में बैठ सकती है। अगर दो अलग अक्षरों की एक-एक बचट हो, दो बीच चाहिए। एक लाइन में सिर्फ एक मध्य सीट होती है।

नियम सीधा है:

• हर अक्षर की गिनती सम हो, या
• ठीक एक अक्षर की गिनती विषम हो (बाकी सम)।

यही पूरा एल्गोरिदम है, एक बार तय हो जाए कि क्या गिनना है (केवल अक्षर? केस? स्पेस?)।

---

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

इनपुट: एक स्ट्रिंग s।

आउटपुट: true अगर s के अक्षरों का कोई फेरबदल पैलिंड्रोम बनाता है; वरना false।

इंटरव्यू में पूछने लायक स्पष्टीकरण

सवाल	सामान्य शिक्षण विकल्प
स्पेस?	अक्सर छोड़ देते हैं (Tact Coa जैसी पंक्ति → tacocat)
केस?	अक्सर केस-असंवेदनशील (T और t एक ही अक्षर)
खाली स्ट्रिंग?	आमतौर पर true (खाली पैलिंड्रोम है)
केवल एएससीआईआई अक्षर?	पूछो; सामान्य मैप किसी भी अक्षर-सेट पर चलता है

क्लासिक उदाहरण: "Tact Coa" को "taco cat" में फेरबदल कर सकते हो (स्पेस और केस छोड़कर), इसलिए उत्तर true है।

तुमसे पैलिंड्रोम स्ट्रिंग लौटाने को नहीं कहा गया। सिर्फ हां या ना।

---

कोड से पहले कैसे सोचें

ब्रूट फोर्स (यह मत भेजो)

हर परम्यूटेशन बनाओ और isPalindrome चेक करो। समय फैक्टोरियल है। इंटरव्यूअर चाहते हैं कि एक बार जिक्र करो और छोड़ दो।

बेहतर विचार: मध्य-सीट वाला नियम

१. हर अक्षर कितनी बार आया, गिनो।
२. कितने अक्षरों की आवृत्ति विषम है, गिनो।
३. अगर वह विषम गिनती ० या १ है तो स्वीकार करो।

क्यों काफी है:

• सम लंबाई का पैलिंड्रोम: हर जोड़ा मिलता है; शून्य विषम।
• विषम लंबाई का पैलिंड्रोम: एक अक्षर बीच में; ठीक एक विषम।

स्ट्रिंग बनानी नहीं पड़ती। सिर्फ गिनती देखो।

वैकल्पिक बिट-वेक्टर (अगर वर्णमाला छोटी हो)

अगर सिर्फ अंग्रेजी छोटे अक्षर मायने रखते हैं, int में बिट टॉगल कर सकते हो (२६ बिट समा जाते हैं)। सम गिनती पर बिट ०, विषम पर १। अंत में सेट में अधिकतम एक बिट होना चाहिए (x & (x - 1) == 0)। वर्णमाला तय हो तो इंटरव्यू में अच्छा। नीचे वाला मैप संस्करण साफ और सामान्य है।

---

जावा हल: विषम गिनो

यह संस्करण अक्षरों को लोअरकेस करता है, गैर-अक्षर छोड़ता है, और HashMap इस्तेमाल करता है। अगर इंटरव्यूअर हर कैरेक्टर चाहे (स्पेस सहित), फिल्टर बदलो।

import java.util.HashMap;
import java.util.Map;

public class PalindromePermutation {

    /**
     * Returns true if some permutation of the letters in s is a palindrome.
     * Spaces and punctuation are ignored. Case is ignored.
     */
    public static boolean isPalindromePermutation(String s) {
        if (s == null) {
            return false;
        }

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

        int oddCount = 0;
        for (int freq : counts.values()) {
            if (freq % 2 != 0) {
                oddCount++;
                if (oddCount > 1) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isPalindromePermutation("Tact Coa")); // true  (taco cat)
        System.out.println(isPalindromePermutation("hello"));    // false
        System.out.println(isPalindromePermutation("aab"));      // true  (aba)
        System.out.println(isPalindromePermutation(""));         // true
        System.out.println(isPalindromePermutation("Aa"));       // true  (aa / Aa)
    }
}

चलकर देखो: "Tact Coa"

छोड़ने और लोअरकेस के बाद अक्षर: t a c t c o a

अक्षर	गिनती
a	२
c	२
o	१
t	२

विषम आवृत्ति: सिर्फ o। एक मध्य सीट ठीक है। true लौटाओ।

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

h:१ e:१ l:२ o:१ → तीन विषम। असंभव। false लौटाओ।

तय वर्णमाला के साथ बिट मास्क

वही विचार, बिना HashMap, नॉर्मलाइज के बाद सिर्फ a-z के लिए:

public static boolean isPalindromePermutationBits(String s) {
    if (s == null) {
        return false;
    }
    int bitVector = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (!Character.isLetter(c)) {
            continue;
        }
        int idx = Character.toLowerCase(c) - 'a';
        if (idx < 0 || idx >= 26) {
            continue; // non a-z after lowercasing
        }
        bitVector ^= (1 << idx); // flip: even -> odd, odd -> even
    }
    // zero or one bit set
    return bitVector == 0 || (bitVector & (bitVector - 1)) == 0;
}

x & (x - 1) सबसे निचला सेट बिट साफ करता है। अगर परिणाम शून्य है, x में शून्य या एक बिट सेट था।

---

समय और स्थान

तरीका	समय	अतिरिक्त स्थान	नोट
मैप से गिनती	ओ(एन)	ओ(के) अलग अक्षर	साफ डिफ़ॉल्ट जवाब
int[26] से गिनती	ओ(एन)	ओ(१)	जब वर्णमाला तय लैटिन अक्षर हो
बिट वेक्टर	ओ(एन)	ओ(१)	वही तय वर्णमाला; चतुर पर गड़बड़ आसान
सभी परम्यूटेशन	ओ(एन · एन!)	ओ(एन) रिकर्शन	जिक्र करो, फिर छोड़ो

गिनती के लिए एक पास और कुंजियों पर छोटा पास (या चलती विषम गिनती) काफी है। मैप अपडेट करते समय oddCount भी रख सकते हो अगर एक संरचनात्मक लूप पसंद हो।

---

किनारे के केस जो इंटरव्यूअर छूते हैं

• नल: व्यवहार तय करो (false या थ्रो)। जोर से बोलो।
• खाली / सिर्फ स्पेस: फिल्टर के बाद कोई विषम नहीं → true।
• एक अक्षर: एक विषम → true।
• सभी गिनती सम: true (सम लंबाई पैलिंड्रोम)।
• दो विषम: false।
• यूनिकोड / उच्चारण: Character.isLetter और toLowerCase लोकैल के साथ सूक्ष्म हैं। इंटरव्यू में जब तक पूरा यूनिकोड न मांगे, एएससीआईआई मान लो।
• पैलिंड्रोम में स्पेस शामिल करने हों: तब स्पेस मत छोड़ो; स्पेस भी एक अक्षर है जिसकी भूमिका सम या एकमात्र विषम हो सकती है।
• केस संवेदनशील: अगर समस्या कहे तो toLowerCase हटा दो।

कोड से पहले नियम दोबारा बोलो। इस समस्या पर आधी गलतियां गलत धारणाएं हैं, गलत गणित नहीं।

---

आम गलतियां

१. संभावना जांचने के बजाय पैलिंड्रोम बनाना। समय की बर्बादी।
२. भूलना कि शून्य विषम वैध है (सम लंबाई)।
३. जब उदाहरण स्पष्ट रूप से स्पेस छोड़ता हो तब स्पेस गिनना (या उलटा)।
४. केस बेमेल: जब समस्या एक माने तब T और t अलग गिनना।
५. बिना तय वर्णमाला के बिट ट्रिक। जब तक वर्णमाला सीमित न हो, मैप सुरक्षित है।

---

जुड़े विचार

• कोई स्ट्रिंग खुद पैलिंड्रोम है या नहीं, दो पॉइंटर से चेक होता है। वह अलग समस्या है (सीटीसीआई में आगे लिंकड लिस्ट पैलिंड्रोम भी है)।
• एनाग्राम / दूसरी स्ट्रिंग का परम्यूटेशन (समस्या १.२ शैली) दो पूरी आवृत्ति मैप मिलाता है। यहां एक मैप की सम-विषमता काफी है।
• किसी बहु-समूह से बनाया जा सकने वाला सबसे लंबा पैलिंड्रोम निकट संबंधी है: सारी सम गिनती लो, बीच के लिए अधिकतम एक विषम बचट।

---

दोस्त को समझाओ

तुम्हें अक्षर की टाइलें मिलीं। क्या उन्हें लाइन कर सकते हो ताकि शब्द खुद को आईने में देखे?

मिलती सीटों के लिए जोड़े चाहिए। सिर्फ एक अक्षर को बीच के लिए एक बचट टाइल मिल सकती है। हर अक्षर गिनो। अगर एक से ज्यादा अक्षर की गिनती विषम है, ना कहो। वरना हां।

जावा में: स्ट्रिंग चलाओ, अक्षर गिनो (आमतौर पर लोअरकेस, स्पेस छोड़कर), फिर देखो अधिकतम एक आवृत्ति विषम हो। समय ओ(एन) है और परम्यूटेशन बनानी नहीं पड़ती।

श्रृंखला में अगला: वन अवे। श्रृंखला नक्शा: जावा में सीटीसीआई।