ప్రస్తారణలతో పాలిండ్రోమ్ ఏర్పడటానికి కనీస చొప్పనలు అనుమతించబడతాయి


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్ కోడ్‌నేషన్ డైరెక్టి గూగుల్ నిజానికి Intuit
డైనమిక్ ప్రోగ్రామింగ్ స్ట్రింగ్

“ప్రస్తారణలతో పాలిండ్రోమ్‌ను రూపొందించడానికి కనీస చొప్పనలు” సమస్య మీకు చిన్న అక్షరాలతో అన్ని అక్షరాలతో స్ట్రింగ్ ఇవ్వబడిందని పేర్కొంది. సమస్య ప్రకటన స్ట్రింగ్‌కు కనీస చొప్పించడాన్ని తెలుసుకోవడానికి అడుగుతుంది, అది పాలిండ్రోమ్‌గా మారుతుంది. అక్షరాల స్థానాన్ని స్ట్రింగ్‌లో మార్చవచ్చు.

ఉదాహరణ

ప్రస్తారణలతో పాలిండ్రోమ్ ఏర్పడటానికి కనీస చొప్పనలు అనుమతించబడతాయి

malyalam
1

వివరణ

ప్రారంభ స్ట్రింగ్‌కు మనం 'a' ను జోడించగలిగితే, మనం పాలిండ్రోమ్‌ను సృష్టించవచ్చు.

madaam
1

వివరణ

అసలు స్ట్రింగ్ పాలిండ్రోమ్ చేయడానికి 'd' లేదా 'a' ను జోడించండి.

అల్గారిథం

  1. స్ట్రింగ్ యొక్క పొడవును సెట్ చేయండి l మరియు అవుట్పుట్ 0 కు.
  2. ఒక ప్రకటించండి పూర్ణ సంఖ్య అమరిక.
  3. ప్రతి అక్షరం యొక్క సంఖ్యను స్ట్రింగ్‌లో నిల్వ చేయండి మరియు నిర్వహించండి.
  4. నేను <0 అయితే 26 నుండి మొదలుకొని శ్రేణిని దాటండి.
    1. తనిఖీ చేయండి కౌంట్చార్ [i] % 2 == 1,
      1. నిజమైతే, అవుట్పుట్ ++ చేయండి.
  5. అవుట్పుట్ 0 కి సమానంగా ఉంటే, అప్పుడు 0 తిరిగి ఇవ్వండి.
  6. లేకపోతే రిటర్న్ అవుట్పుట్ -1.

వివరణ

మీకు ఇవ్వబడింది a స్ట్రింగ్, మీ పని ఏమిటంటే, స్ట్రింగ్‌లో చేయవలసిన కనీస చొప్పించడాన్ని కనుగొనడం, తద్వారా ఇది పాలిండ్రోమ్ అవుతుంది. అక్షరాల స్థానాన్ని స్ట్రింగ్‌లో మార్చవచ్చు. మేము స్ట్రింగ్ యొక్క అక్షరం సంభవించడాన్ని లెక్కించి దానిని శ్రేణికి నిల్వ చేయబోతున్నాము. ఎందుకంటే వెనుక ఉన్న ఆలోచన ఏమిటంటే, స్ట్రింగ్ పాలిండ్రోమ్ అయినప్పుడు, స్ట్రింగ్ పొడవు బేసి అయినప్పుడు బేసిగా ఉండే ఒకే అక్షరం మాత్రమే ఉంటుంది. అలా కాకుండా అన్ని అక్షరాలు కూడా ఫ్రీక్వెన్సీని కలిగి ఉంటాయి. కాబట్టి బేసి సంఖ్యలో సంభవించే అక్షరాలను మనం కనుగొనాలి.

మేము ఇన్పుట్ స్ట్రింగ్లోని ప్రతి అక్షరాన్ని లెక్కించి దానిని శ్రేణికి నిల్వ చేయబోతున్నాము. మేము ఇప్పటికే చెప్పినట్లుగా, పాలిండ్రోమ్ అయిన స్ట్రింగ్ బేసి సంఖ్యలో సంభవించే ఒక అక్షరాన్ని మాత్రమే కలిగి ఉంటుంది. కాబట్టి అవుట్పుట్ అక్షరాల సంఖ్య కంటే ఒకటి తక్కువగా ఉంటుంది. ప్రతి అక్షర స్ట్రింగ్ సంఘటనను శ్రేణిలో నిల్వ చేసిన తర్వాత. మేము అప్పుడు i = 0 నుండి i వరకు 26 కన్నా తక్కువ ప్రయాణించే శ్రేణిని తయారు చేస్తున్నాము. దీనికి కారణం మొత్తం 26 అక్షరాలు మరియు ఇచ్చిన స్ట్రింగ్‌లో 26 అక్షరాలు సంభవించే సంభావ్యత ఉంటుందని మనం అనుకోవాలి.

శ్రేణిని దాటుతున్నప్పుడు, ప్రతి గణనను 2 ద్వారా విభజించడం మిగిలిన 1 ని నిజమైతే వదిలివేస్తుందో లేదో మేము తనిఖీ చేస్తాము, అప్పుడు అది అవుట్పుట్ గణనను 1 (అవుట్పుట్ ++) పెంచుతుంది. శ్రేణిని దాటిన తరువాత, గణన సున్నాగా మిగిలి ఉంటే, బేసి అయిన అక్షరాలలో మనకు ఏమీ కనిపించదు అంటే స్ట్రింగ్ ఇప్పటికే పాలిండ్రోమ్ అని అర్ధం, మనం 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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై)  (ఇక్కడ  “N” ఇన్పుట్ స్ట్రింగ్లోని అక్షరాల సంఖ్య.

అంతరిక్ష సంక్లిష్టత

ఓ (1), ఎందుకంటే మేము స్థిరమైన పరిమాణాన్ని కలిగి ఉన్న అదనపు శ్రేణిని సృష్టించాము. అందువలన స్థల సంక్లిష్టత స్థిరంగా ఉంటుంది.