کوچکترین Palindrome پس از تعویض


سطح دشواری ساده
اغلب در خشت ارسیسیوم Flipkart GE بهداشت و درمان ZScaler
پالیندروم رشته

بیان مسأله

در مسئله "کوچکترین Palindrome پس از جایگزینی" ما ورودی داده ایم رشته شامل حروف کوچک حروف و نقطه (.) است. باید تمام نقاط را با برخی از حروف الفبا جایگزین کنیم به این ترتیب که رشته حاصل به palindrome تبدیل شود. پالیندروم باید از نظر لغت نامه کوچکترین

قالب ورودی

اولین و تنها یک خط حاوی رشته ورودی s.

فرمت خروجی

کوچکترین رشته فرهنگ نامه را که یک palindrome است چاپ کنید. اگر چنین رشته ای تشکیل نشده است ، چاپ کنید "ممکن نیست".

محدودیت ها

  • 1 <= | s | <= 10 ^ 6
  • s [i] حروف کوچک حروف یا نقطه است ".

مثال

a..b.a
aabbaa

شرح: برای این رشته ، کوچکترین palindrome است "aabbaa". در اینجا ما s [i] و s [n-1-i] را با «a» جایگزین می کنیم اگر هر دو char نقطه باشد (.). اگر یکی از آنها یک کاراکتر نقطه است ، آن را با یک شخصیت غیر نقطه دیگر جایگزین کنید.

a..b.c
Not possible

شرح: در این رشته ، به راحتی می توانیم ببینیم که اولین و آخرین کاراکتر یکسان نیستند بنابراین نمی توانیم این رشته را به یک رشته پالیندروم تبدیل کنیم. بنابراین ، ما جواب را به صورت چاپ می کنیم "ممکن نیست".

الگوریتم برای کوچکترین Palindrome پس از جایگزینی

1. نادیده گرفتن نویسه های نقطه را با جفت کاراکترهای غیر نقطه بررسی کنید.

  •  اگر چپ و راست هر دو نقطه ای نیستند و برابر نیستند ، False را برگردانید.
  • دیگر ، تا اواسط عبور کنید.
  • اگر به پایان رسید ، درست را برگردانید.

2. اگر هر دو موقعیت "i" و "ni-1" نقطه باشند ، آنها را با "a" جایگزین کنید.

3. در غیر این صورت ، اگر یکی از آنها نویسه نقطه باشد ، آن را با یک نویسه غیر نقطه ای دیگر جایگزین کنید.

4. رشته نهایی را برگردانید.

پیاده سازی

برنامه C ++ برای Smallest Palindrome پس از تعویض

#include<bits/stdc++.h>
using namespace std;
int main()
{
   string s;
   cin>>s;
   int n=s.length();
   int flag=0;
   for(int i=0;i<n/2;i++)
   {
       if(s[i]!='.' && s[n-1-i]!='.' && s[i]!=s[n-1-i])
       {
           flag=1;
           break;
       }
   }
   if(flag==1)
   {
       cout<<"Not possible"<<endl;
   }
   else
   {
       for(int i=0;i<n;i++)
       {
           if(s[i]=='.')
           {
               if(s[n-1-i]=='.')
               {
                   s[i]='a';
                   s[n-1-i]='a';
               }
               else
               {
                   s[i]=s[n-1-i];
               }
           }
       }
       cout<<s<<endl;
   }
   return 0;
}

برنامه جاوا برای Smallest Palindrome پس از تعویض

import java.util.Scanner;

class sum {
    
    public static void main(String[] args) 
    {
        Scanner sr= new Scanner(System.in);
        String s = sr.next();
        int n = s.length();
        char a[] = s.toCharArray();
        int flag=0;
        for(int i=0;i<n/2;i++)
        {
            if(a[i]!='.' && a[n-1-i]!='.' && a[i]!=a[n-1-i])
            {
                flag=1;
                break;
            }
        }
        if(flag==1)
        {
            System.out.println("Not possible");
        }
        else
        {
            for(int i=0;i<n;i++)
            {
                if(a[i]=='.')
                {
                    if(a[n-1-i]=='.')
                    {
                        a[i]='a';
                        a[n-1-i]='a';
                    }
                    else
                    {
                        a[i]=a[n-1-i];
                    }
                }
            }
            for(int i=0;i<n;i++)
            {
                System.out.print(a[i]);
            }
            System.out.println();
        }
    } 
}
a..b.a
aabbaa

تجزیه و تحلیل پیچیدگی برای کوچکترین Palindrome پس از جایگزینی

پیچیدگی زمان

O (N) جایی که n اندازه رشته داده شده است "s". در اینجا ما فقط رشته داده شده را رد می کنیم و کارهای مفید را انجام می دهیم.

پیچیدگی فضا

O (1) زیرا ما در اینجا از فضای اضافی استفاده نمی کنیم. که ما را به سمت پیچیدگی فضا ثابت می برد.