অনুমোদনের অনুমতি সহ প্যালিনড্রোম গঠনের সর্বনিম্ন সন্নিবেশ


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক কোডনেশন ডাইরেক্টি গুগল প্রকৃতপক্ষে যুক্তি তর্ক
ডায়নামিক প্রোগ্রামিং স্ট্রিং

"অনুমতি দেওয়া ছাড়াই একটি প্যালিনড্রোম গঠনের ন্যূনতম সন্নিবেশ" সমস্যাটি বলে যে আপনাকে ছোট হাতের অক্ষরে সমস্ত অক্ষর সহ একটি স্ট্রিং দেওয়া হয়। সমস্যার বিবৃতিটি কোনও স্ট্রিংয়ে কোনও চরিত্রের ন্যূনতম সন্নিবেশ সন্ধান করতে বলে যে এটি প্যালিনড্রোমে পরিণত হতে পারে। অক্ষরের অবস্থান একটি স্ট্রিংয়ে পরিবর্তন করা যেতে পারে।

উদাহরণ

অনুমোদনের অনুমতি সহ প্যালিনড্রোম গঠনের সর্বনিম্ন সন্নিবেশ

malyalam
1

ব্যাখ্যা

আমরা যদি প্রাথমিক স্ট্রিংয়ে 'এ' যুক্ত করতে পারি তবে আমরা একটি প্যালিনড্রোম তৈরি করতে পারি।

madaam
1

ব্যাখ্যা

মূল স্ট্রিং প্যালিনড্রোম তৈরি করতে হয় 'd' বা 'এ' যুক্ত করুন।

অ্যালগরিদম

  1. স্ট্রিংয়ের দৈর্ঘ্য সেট করুন l এবং আউটপুট 0।
  2. ঘোষণা করুন an পূর্ণসংখ্যা বিন্যাস.
  3. স্ট্রিংয়ে প্রতিটি চরিত্রের গণনা সংরক্ষণ এবং বজায় রাখুন।
  4. আমি <0 যখন 26 থেকে শুরু করে অ্যারেটি অতিক্রম করুন।
    1. চেক করুন যদি কাউন্টচর [i] % 2 == 1,
      1. যদি সত্য হয়, তবে আউটপুট ++ করুন।
  5. যদি আউটপুট 0 এর সমান হয় তবে 0 তে ফিরে আসুন।
  6. অন্য রিটার্ন আউটপুট -১।

ব্যাখ্যা

আপনি একটি দেওয়া হয় স্ট্রিং, আপনার দেওয়া কাজটি হ'ল স্ট্রিংয়ে করা সর্বনিম্ন সন্নিবেশ সন্ধান করা যাতে এটি প্যালিনড্রোমে পরিণত হয়। অক্ষরের অবস্থান একটি স্ট্রিংয়ে পরিবর্তন করা যেতে পারে। আমরা একটি স্ট্রিং এর চরিত্রের উপস্থিতি গণনা করতে এবং এটি একটি অ্যারেতে সঞ্চয় করতে যাচ্ছি। কারণ পিছনে ধারণাটি হ'ল স্ট্রিংটি যখন প্যালিনড্রোম হয় তখন কেবলমাত্র একটি একক অক্ষর থাকে যা স্ট্রিংয়ের দৈর্ঘ্যটি বিজোড় হলে অদ্ভুত হতে পারে। এটি বাদে সমস্ত অক্ষরের এমনকি ফ্রিকোয়েন্সিও রয়েছে। সুতরাং আমাদের এমন একটি অক্ষর খুঁজে বার করতে হবে যা একটি অদ্ভুত সংখ্যক বার ঘটে।

আমরা ইনপুট স্ট্রিংয়ের প্রতিটি অক্ষর গণনা করতে যাচ্ছি এবং এটি একটি অ্যারেতে সঞ্চয় করব। যেমনটি আমরা ইতিমধ্যে উল্লেখ করেছি, একটি স্ট্রিং যা প্যালিনড্রোম কেবল তার মধ্যে একটি অক্ষর থাকতে পারে যা বেজোড় সংখ্যক বার ঘটে। সুতরাং আউটপুট অক্ষর গণনা থেকে এক কম হবে। একটি অ্যারে প্রতিটি অক্ষর স্ট্রিং ঘটনা সংরক্ষণ করার পরে। তারপরে আমরা i = 0 থেকে i এর চেয়ে 26 এর চেয়ে কম একটি অ্যারে তৈরি করছি ing এটি মোট 26 টি অক্ষর কারণ আমাদের মনে করা উচিত যে একটি নির্দিষ্ট স্ট্রিংয়ে 26 টি অক্ষরের উপস্থিতি হওয়ার সম্ভাবনা রয়েছে।

অ্যারেটি ট্র্যাভার করার সময় আমরা যাচাই করব যে প্রতিটি গণনা 2 টি দিয়ে ভাগ করে নেওয়া যদি বাকি 1 টি বাকী থাকে তবে এটি সত্য হয়, তবে এটি আউটপুটের গণনা 1 (আউটপুট ++) দ্বারা বাড়িয়ে দেবে। একটি অ্যারে অনুসরণ করার পরে, যদি গণনাটি শূন্য হিসাবে থেকে যায়, এর অর্থ আমরা অক্ষরে কিছুই খুঁজে পাই না যা বিজোড় মানে স্ট্রিং ইতিমধ্যে প্যালিনড্রোম, আমরা 0 আবার ফিরে আসব আমরা ইতিমধ্যে উল্লিখিত আউটপুটটির চেয়ে কম হবে অক্ষর গণনা এবং সুতরাং আমরা আউটপুট পেয়েছি।

কোড

সি ++ কোড ন্যূনতম সন্নিবেশগুলি পলিনড্রোম গঠনের অনুমতি সহ অনুমতি দেয় find

#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

জটিলতা বিশ্লেষণ

সময় জটিলতা

উপর) কোথায় "এন" ইনপুট স্ট্রিংয়ের অক্ষরের সংখ্যা।

স্পেস জটিলতা ity

ও (1), কারণ আমরা ধ্রুব আকারযুক্ত একটি অতিরিক্ত অ্যারে তৈরি করেছি। সুতরাং স্থান জটিলতা ধ্রুবক।