परवानगी असलेल्या परवान्यांसह पॅलिंड्रोम तयार करण्यासाठी किमान अंतर्भूत माहिती


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन CodeNation डायरेक्टि Google खरंच अंतर्ज्ञानाने जाणणे
डायनॅमिक प्रोग्रामिंग अक्षरमाळा

“अनुमत परवान्यांसह पॅलिंड्रोम तयार करण्यासाठी किमान अंतर्भूत माहिती” ही समस्या सांगते की आपल्याला लोअरकेसमध्ये सर्व अक्षरे असलेले एक स्ट्रिंग दिले गेले आहे. समस्या स्टेटमेंटमध्ये पात्राची पात्राइंड्रोम होऊ शकते अशा स्ट्रिंगमध्ये कमीतकमी अंतर्भूत माहिती शोधण्यास सांगते. अक्षरांची स्थिती स्ट्रिंगमध्ये बदलली जाऊ शकते.

उदाहरण

परवानगी असलेल्या परवान्यांसह पॅलिंड्रोम तयार करण्यासाठी किमान अंतर्भूत माहिती

malyalam
1

स्पष्टीकरण

जर आपण प्रारंभिक स्ट्रिंगमधे 'a' जोडू शकतो, तर आपण पालिंड्रोम तयार करू शकतो.

madaam
1

स्पष्टीकरण

एकतर मूळ स्ट्रिंग पॅलिंड्रोम करण्यासाठी 'डी' किंवा 'ए' जोडा.

अल्गोरिदम

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

स्पष्टीकरण

आपल्याला दिले जाते a स्ट्रिंग, आपले कार्य दिले गेले आहे की स्ट्रिंगमध्ये कमीतकमी अंतर्भूत माहिती शोधणे जेणेकरून ते पालिंड्रोम होईल. अक्षरांची स्थिती स्ट्रिंगमध्ये बदलली जाऊ शकते. आम्ही स्ट्रिंगच्या कॅरेक्टरच्या घटनेची मोजणी करणार आहोत आणि ती अ‍ॅरे मध्ये संचित करणार आहोत. कारण यामागची कल्पना अशी आहे की जेव्हा स्ट्रिंग पॅलिंड्रोम असते, तेव्हा केवळ एकच वर्ण असते जेव्हा स्ट्रिंगची लांबी विचित्र असते तेव्हा विचित्र असू शकते. त्याशिवाय सर्व पात्रांची वारंवारता देखील असते. म्हणून आम्हाला विचित्र संख्येने आढळणारी अक्षरे शोधणे आवश्यक आहे.

आम्ही इनपुट स्ट्रिंगमधील प्रत्येक अक्षरे मोजू आणि त्यास अ‍ॅरे मध्ये संचयित करणार आहोत. आम्ही आधीच नमूद केल्याप्रमाणे, पालिंड्रोम असलेल्या स्ट्रिंगमध्ये फक्त एक वर्ण असू शकतो जो विचित्र वेळा आढळतो. तर आऊटपुट कॅरेक्टरच्या मोजणीपेक्षा कमी असेल. अ‍ॅरेमध्ये प्रत्येक कॅरेक्टर स्ट्रिंग इव्हेंटन्स संचित केल्यावर. आम्ही नंतर आय = 0 ते i पर्यंत 26 पेक्षा कमी असलेले अ‍ॅरे बनवित आहोत. हे असे आहे कारण एकूण 26 वर्ण आहेत आणि आपण समजू शकतो की दिलेल्या स्ट्रिंगमध्ये 26 अक्षरे येण्याची शक्यता आहे.

अ‍ॅरे ट्रॅव्हर्स करताना, आम्ही तपासू की प्रत्येक मोजणी 2 ने विभाजित केल्यावर उर्वरित 1 बाकी आहे की ते बरोबर असल्यास ते आऊटपुटची संख्या 1 (आउटपुट ++) ने वाढवेल. Traरेचा शोध घेतल्यानंतर, जर गणना शून्य राहिली तर याचा अर्थ असा आहे की आपल्याकडे अक्षरात काहीही नाही जे स्ट्रिंग आधीपासून पॅलिंड्रोम आहे, आम्ही 0 परत मिळवू (आउटपुट -1) आम्ही आधीच नमूद केल्याप्रमाणे आउटपुट एकापेक्षा कमी असेल. कॅरेक्टरची संख्या आणि म्हणून आपल्याला आऊटपुट मिळाले.

कोड

अनुमत परवान्यांसह पॅलिंड्रोम तयार करण्यासाठी किमान अंतर्भूत माहिती शोधण्यासाठी सी ++ कोड

#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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n) जेथे “एन” इनपुट स्ट्रिंगमधील वर्णांची संख्या आहे.

स्पेस कॉम्प्लेक्सिटी

ओ (1), कारण आम्ही सतत आकार असणारी एक अतिरिक्त अ‍ॅरे तयार केली आहे. अशा प्रकारे जागेची जटिलता स्थिर आहे.