പെർ‌മ്യൂട്ടേഷനുകൾ അനുവദനീയമായ ഒരു പലിൻഡ്രോം രൂപീകരിക്കുന്നതിനുള്ള ഏറ്റവും കുറഞ്ഞ ഉൾപ്പെടുത്തലുകൾ  


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ കോഡ്നേഷൻ ഡയറക്റ്റി ഗൂഗിൾ തീർച്ചയായും Intuit
ഡൈനാമിക് പ്രോഗ്രാമിംഗ് സ്ട്രിംഗ്

“അനുവദനീയമായ ക്രമീകരണം ഉള്ള ഒരു പലിൻഡ്രോം രൂപീകരിക്കുന്നതിനുള്ള ഏറ്റവും കുറഞ്ഞ ഉൾപ്പെടുത്തലുകൾ” എന്ന പ്രശ്‌നം, ചെറിയ അക്ഷരങ്ങളിലുള്ള എല്ലാ അക്ഷരങ്ങളും ഉൾക്കൊള്ളുന്ന ഒരു സ്ട്രിംഗ് നിങ്ങൾക്ക് നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു. ഒരു പ്രതീകം പലിൻഡ്രോം ആകാൻ സാധ്യതയുള്ള ഒരു സ്‌ട്രിംഗിലേക്ക് ഏറ്റവും കുറഞ്ഞ ഉൾപ്പെടുത്തൽ കണ്ടെത്താൻ പ്രശ്‌ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു. പ്രതീകങ്ങളുടെ സ്ഥാനം ഒരു സ്ട്രിംഗിൽ മാറ്റാം.

ഉദാഹരണം  

പെർ‌മ്യൂട്ടേഷനുകൾ അനുവദനീയമായ ഒരു പലിൻഡ്രോം രൂപീകരിക്കുന്നതിനുള്ള ഏറ്റവും കുറഞ്ഞ ഉൾപ്പെടുത്തലുകൾമൊട്ടുസൂചി

malyalam
1

വിശദീകരണം

പ്രാരംഭ സ്ട്രിംഗിലേക്ക് നമുക്ക് 'a' ചേർക്കാൻ കഴിയുമെങ്കിൽ, നമുക്ക് ഒരു പലിൻഡ്രോം സൃഷ്ടിക്കാൻ കഴിയും.

madaam
1

വിശദീകരണം

ഒറിജിനൽ സ്ട്രിംഗ് പലിൻഡ്രോം നിർമ്മിക്കുന്നതിന് 'd' അല്ലെങ്കിൽ 'a' ചേർക്കുക.

അൽഗോരിതം  

  1. സ്ട്രിംഗിന്റെ ദൈർഘ്യം സജ്ജമാക്കുക l output ട്ട്‌പുട്ട് 0 ആയി.
  2. ഒരു പ്രഖ്യാപിക്കുക പൂർണ്ണസംഖ്യ ശ്രേണി.
  3. ഓരോ പ്രതീകത്തിന്റെയും എണ്ണം ഒരു സ്‌ട്രിംഗിൽ സംഭരിക്കുകയും പരിപാലിക്കുകയും ചെയ്യുക.
  4. 0 മുതൽ ആരംഭിച്ച് ഞാൻ <26 വരെ അറേയിലൂടെ സഞ്ചരിക്കുക.
    1. പരിശോധിക്കുക countChar [i] % 2 == 1,
      1. ശരിയാണെങ്കിൽ output ട്ട്‌പുട്ട് ++ ചെയ്യുക.
  5. 0 ട്ട്‌പുട്ട് 0 ന് തുല്യമാണെങ്കിൽ, XNUMX നൽകുക.
  6. അല്ലെങ്കിൽ റിട്ടേൺ output ട്ട്‌പുട്ട് -1.

വിശദീകരണം

നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ട് സ്ട്രിംഗ്, നിങ്ങളുടെ ചുമതല നൽകിയിരിക്കുന്നത് ഒരു സ്ട്രിംഗിൽ ചെയ്യേണ്ട ഏറ്റവും കുറഞ്ഞ ഉൾപ്പെടുത്തൽ കണ്ടെത്തുന്നതിലൂടെ അത് ഒരു പലിൻഡ്രോം ആയി മാറുന്നു. പ്രതീകങ്ങളുടെ സ്ഥാനം ഒരു സ്ട്രിംഗിൽ മാറ്റാം. ഒരു സ്ട്രിംഗിന്റെ പ്രതീകത്തിന്റെ സംഭവം ഞങ്ങൾ കണക്കാക്കി അതിനെ ഒരു അറേയിൽ സംഭരിക്കാൻ പോകുന്നു. കാരണം, ഒരു സ്ട്രിംഗ് ഒരു പലിൻഡ്രോം ആയിരിക്കുമ്പോൾ, സ്ട്രിംഗ് ദൈർഘ്യം വിചിത്രമാകുമ്പോൾ ഒറ്റ ആകൃതി മാത്രമേ ഉണ്ടാകൂ എന്നതാണ് പിന്നിലെ ആശയം. ഇതുകൂടാതെ എല്ലാ പ്രതീകങ്ങൾക്കും ആവൃത്തി പോലും ഉണ്ട്. അതിനാൽ, വിചിത്രമായ തവണ സംഭവിക്കുന്ന പ്രതീകങ്ങൾ ഞങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട്.

ഇതും കാണുക
സ്റ്റോൺ ഗെയിം II ലീറ്റ്കോഡ്

ഇൻപുട്ട് സ്‌ട്രിംഗിലെ എല്ലാ പ്രതീകങ്ങളും ഞങ്ങൾ കണക്കാക്കി ഒരു അറേയിൽ സംഭരിക്കാൻ പോകുന്നു. ഞങ്ങൾ ഇതിനകം സൂചിപ്പിച്ചതുപോലെ, പലിൻഡ്രോം ആയ ഒരു സ്‌ട്രിംഗിന് ഒറ്റ പ്രതീകം മാത്രമേ ഉണ്ടാകൂ, അത് ഒറ്റ തവണ മാത്രം സംഭവിക്കുന്നു. അതിനാൽ character ട്ട്‌പുട്ട് പ്രതീകങ്ങളുടെ എണ്ണത്തേക്കാൾ കുറവായിരിക്കും. എല്ലാ പ്രതീക സ്ട്രിംഗ് സംഭവങ്ങളും ഒരു അറേയിൽ സംഭരിച്ച ശേഷം. I = 0 മുതൽ i വരെ 26 ൽ താഴെയാണ് ഞങ്ങൾ ഒരു അറേ നിർമ്മിക്കുന്നത്. ഇതിന് കാരണം ആകെ 26 പ്രതീകങ്ങൾ ഉള്ളതിനാലാണ്, തന്നിരിക്കുന്ന ഒരു സ്ട്രിംഗിൽ 26 പ്രതീകങ്ങൾ ഉണ്ടാകാനുള്ള സാധ്യതയുണ്ടെന്ന് ഞങ്ങൾ കരുതണം.

അറേയിലൂടെ സഞ്ചരിക്കുമ്പോൾ, ഓരോ എണ്ണവും 2 കൊണ്ട് ഹരിച്ചാൽ ബാക്കി 1 അവശേഷിക്കുന്നുണ്ടോയെന്ന് പരിശോധിക്കും, അത് ശരിയാണെങ്കിൽ, അത് output ട്ട്‌പുട്ടിന്റെ എണ്ണം 1 വർദ്ധിപ്പിക്കും (output ട്ട്‌പുട്ട് ++). ഒരു ശ്രേണിയിലൂടെ സഞ്ചരിച്ചതിനുശേഷം, എണ്ണം പൂജ്യമായി തുടരുകയാണെങ്കിൽ, വിചിത്രമായ പ്രതീകത്തിൽ ഒന്നും ഞങ്ങൾ കണ്ടെത്തുന്നില്ല എന്നാണ് അർത്ഥമാക്കുന്നത് സ്ട്രിംഗ് ഇതിനകം പലിൻഡ്രോം ആണെന്നാണ്, ഞങ്ങൾ 0 മടങ്ങും, അല്ലെങ്കിൽ ഞങ്ങൾ മടങ്ങും (output ട്ട്പുട്ട് -1) നമ്മൾ നേരത്തെ സൂചിപ്പിച്ചതുപോലെ output ട്ട്‌പുട്ട് ഒരു കുറവ് ആയിരിക്കും പ്രതീകങ്ങളുടെ എണ്ണം അതിനാൽ ഞങ്ങൾക്ക് .ട്ട്‌പുട്ട് ലഭിച്ചു.

കോഡ്  

ക്രമമാറ്റം അനുവദിച്ചുകൊണ്ട് ഒരു പലിൻഡ്രോം രൂപീകരിക്കുന്നതിന് കുറഞ്ഞ ഉൾപ്പെടുത്തലുകൾ കണ്ടെത്തുന്നതിനുള്ള സി ++ കോഡ്

#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) എവിടെ “N” ഇൻപുട്ട് സ്ട്രിംഗിലെ പ്രതീകങ്ങളുടെ എണ്ണം.

ഇതും കാണുക
ഒരു സ്ട്രീമിൽ മികച്ച കെ (അല്ലെങ്കിൽ ഏറ്റവും പതിവ്) നമ്പറുകൾ കണ്ടെത്തുക

ബഹിരാകാശ സങ്കീർണ്ണത

O (1), കാരണം സ്ഥിരമായ വലുപ്പമുള്ള ഒരു അധിക ശ്രേണി ഞങ്ങൾ സൃഷ്ടിച്ചു. അങ്ങനെ സ്ഥല സങ്കീർണ്ണത സ്ഥിരമാണ്.