पायथन में जांचें कि कोई स्ट्रिंग विशेष पैलिंड्रोम बनाने के लिए पुनर्व्यवस्थित की जा सकती है या नहीं

मान लीजिए हमारे पास एक स्ट्रिंग है; हमें यह जांचना है कि क्या दिए गए स्ट्रिंग के वर्णों को फेरबदल (shuffle) करके पैलिंड्रोम बनाया जा सकता है या नहीं।

उदाहरण के लिए, यदि इनपुट s = "aarcrce" है, तो आउटपुट True होगा क्योंकि हम वर्णों को फेरबदल करके "racecar" बना सकते हैं जो एक पैलिंड्रोम है।

समाधान दृष्टिकोण

एक स्ट्रिंग के वर्णों को पुनर्व्यवस्थित करके पैलिंड्रोम बनाया जा सकता है यदि और केवल यदि अधिकतम एक वर्ण की आवृत्ति विषम हो।

एल्गोरिदम चरण:

1. आकार 256 का freq ऐरे बनाएं (ASCII वर्णों के लिए) और 0 से भरें
2. स्ट्रिंग के प्रत्येक वर्ण की आवृत्ति गिनें
3. odd_count = 0
4. प्रत्येक आवृत्ति के लिए:
• यदि आवृत्ति विषम है, तो odd_count += 1
• यदि odd_count > 1, तो False लौटाएं
5. True लौटाएं

पायथन कार्यान्वयन

def solve(s):
    size = 256
    freq = [0] * size
    
    for i in range(len(s)):
        freq[ord(s[i])] += 1
    
    odd_count = 0
    for i in range(size):
        if freq[i] % 2 == 1:
            odd_count += 1
            if odd_count > 1:
                return False
    return True

# collections.Counter का उपयोग करके सरल संस्करण
from collections import Counter

def solve_simple(s):
    freq = Counter(s)
    odd_count = sum(1 for v in freq.values() if v % 2 == 1)
    return odd_count <= 1

s = "aarcrce"
print(solve(s))        # True
print(solve_simple(s)) # True

इनपुट

"aarcrce"

आउटपुट

True

व्याख्या:

"aarcrce" में आवृत्तियां:

• a: 2 (सम)
• r: 2 (सम)
• c: 2 (सम)
• e: 1 (विषम)

केवल एक विषम आवृत्ति (e), इसलिए पैलिंड्रोम संभव है: "racecar"