अनुमति के साथ एक पैलिंड्रोम बनाने के लिए न्यूनतम सम्मिलन


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना कोडेशन डायरेक्टी गूगल वास्तव में सहज
गतिशील प्रोग्रामिंग तार

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

उदाहरण

अनुमति के साथ एक पैलिंड्रोम बनाने के लिए न्यूनतम सम्मिलन

malyalam
1

व्याख्या

यदि हम प्रारंभिक स्ट्रिंग में 'a' जोड़ सकते हैं, तो हम एक palindrome बना सकते हैं।

madaam
1

व्याख्या

मूल स्ट्रिंग तालमेल बनाने के लिए या तो 'डी' या 'ए' जोड़ें।

कलन विधि

  1. स्ट्रिंग की लंबाई निर्धारित करें l और आउटपुट 0 पर है।
  2. डिक्लेयर ए पूर्णांक सरणी.
  3. स्टोर करें और एक स्ट्रिंग में प्रत्येक वर्ण की गिनती बनाए रखें।
  4. सरणी को 0 से शुरू करते हुए i <26 तक ले जाएं।
    1. अगर जांच काउंटचार [i] % 2 == 1,
      1. अगर सच है, तो आउटपुट ++ करें।
  5. यदि आउटपुट 0 के बराबर है, तो 0 वापस करें।
  6. एल्स रिटर्न आउटपुट -1।

व्याख्या

आपको ए स्ट्रिंग, आपका कार्य दिया गया है कि एक स्ट्रिंग में किए जाने वाले न्यूनतम सम्मिलन का पता लगाना है ताकि यह एक पैलिंड्रोम बन जाए। पात्रों की स्थिति को एक स्ट्रिंग में बदला जा सकता है। हम एक स्ट्रिंग के चरित्र की घटना को गिनने और इसे एक सरणी में संग्रहीत करने जा रहे हैं। क्योंकि इसके पीछे विचार यह है कि जब एक स्ट्रिंग एक पैलिंड्रोम होती है, तो केवल एक ही वर्ण होता है जो स्ट्रिंग की लंबाई विषम होने पर विषम हो सकता है। इसके अलावा सभी पात्रों में आवृत्ति भी होती है। इसलिए हमें कई बार विषम संख्या वाले वर्णों को खोजने की आवश्यकता होती है।

हम इनपुट स्ट्रिंग में प्रत्येक वर्ण को गिनने जा रहे हैं और इसे एक ऐरे में स्टोर कर रहे हैं। जैसा कि हमने पहले ही उल्लेख किया है, एक स्ट्रिंग जो पैलिंड्रोम है उसमें केवल एक ही चरित्र हो सकता है जो विषम संख्या में होता है। इसलिए आउटपुट कैरेक्टर काउंट से कम होगा। एक सरणी में हर वर्ण स्ट्रिंग घटना को संग्रहीत करने के बाद। हम तब i = 0 से i तक की एक सारणी बना रहे हैं जो 26 से कम है। ऐसा इसलिए है क्योंकि कुल 26 वर्ण हैं और हमें यह मान लेना चाहिए कि किसी दिए गए स्ट्रिंग में 26 वर्णों के होने की संभावना होगी।

सरणी को ट्रेस करते समय, हम जाँचेंगे कि यदि प्रत्येक गणना को 2 से विभाजित करके शेष 1 छोड़ दिया जाए यदि यह सत्य है, तो यह आउटपुट की संख्या को 1 (आउटपुट ++) से बढ़ा देगा। किसी सरणी को ट्रेस करने के बाद, यदि गिनती शून्य के रूप में रहती है, तो इसका मतलब है कि हमें चरित्र में कुछ भी नहीं मिला है, जो अजीब है, इसका मतलब है कि स्ट्रिंग पहले से ही लंबवत है, हम 0 वापस करेंगे (आउटपुट -1) क्योंकि हम पहले ही उल्लेखित आउटपुट एक से कम होंगे चरित्र की गिनती और इसलिए हमें आउटपुट मिला।

कोड

अनुमतियों के साथ तालमेल बनाने के लिए न्यूनतम सम्मिलन खोजने के लिए C ++ कोड

#include<iostream>

using namespace std;

int getMinimumInsertion(string str)
{
    int l = str.length(),output = 0;

    int countChar[26] = { 0 };
    for (int i = 0; i < l; i++)
        countChar[str[i] - 'a']++;

    for (int i = 0; i < 26; i++)
        if (countChar[i] % 2 == 1)
            output++;

    return (output == 0) ? 0 : output - 1;
}
int main()
{
    string str = "malyalam";
    cout << getMinimumInsertion(str);

    return 0;
}
1

अनुमतियों के साथ तालमेल बनाने के लिए न्यूनतम सम्मिलन खोजने के लिए जावा कोड

class insertionToPalindrome
{
    public static int getMinimumInsertion(String str)
    {
        int l = str.length(),output = 0;

        int countChar[] = new int[26];

        for (int i = 0; i < l; i++)
            countChar[str.charAt(i) - 'a']++;

        for (int i = 0; i < 26; i++)
        {
            if (countChar[i] % 2 == 1)
                output++;
        }

        return (output == 0) ? 0 : output - 1;
    }
    public static void main(String[] args)
    {
        String str = "malyalam";
        System.out.println(getMinimumInsertion(str));
    }
}
1

जटिलता विश्लेषण

समय जटिलता

पर) जहां "N" इनपुट स्ट्रिंग में वर्णों की संख्या है।

अंतरिक्ष जटिलता

ओ (1), क्योंकि हमने एक अतिरिक्त सरणी बनाई है जिसमें निरंतर आकार है। इस प्रकार अंतरिक्ष जटिलता स्थिर है।