Dəyişdirildikdən sonra ən kiçik Palindrom

Problem bəyanat

“Dəyişdirildikdən Sonra Ən Kiçik Palindrom” probleminə giriş verdik sim kiçik hərflərin simvollarını və nöqtələrini (.) ehtiva edir. Bütün nöqtələri bəzi əlifba işarələri ilə elə dəyişdirməliyik ki, nəticələnən sətir palindrom olsun. The palindrom olmalıdır leksikoqrafik cəhətdən ən kiçik.

Giriş Formatı

Giriş sətrini ehtiva edən ilk və yalnız bir sətir.

Çıxış formatı

Palindrom olan ən kiçik lüğət lüğətini çap edin. Əgər belə bir simli yaranmırsa, yazdırın "Mümkün deyil".

Məhdudiyyətlər

• 1 <= | s | <= 10 ^ 6
• s [i] kiçik əlifba simvolları və ya nöqtədir ”.

misal

a..b.a

aabbaa

Explanation: Bu simli üçün ən kiçik palindromdur “Aabbaa”. Burada hər ikisi də nöqtədirsə (.) Olduqda s [i] və s [n-1-i] 'a' ilə əvəz edirik. Bunlardan biri nöqtəli bir xarakterdirsə, onu başqa nöqtəli olmayan bir simvolla əvəz edin.

a..b.c

Not possible

Explanation: Bu sətirdə asanlıqla birinci və son cizgilərin eyni olmadığını görə bilərik, çünki bu sətri palindrom sətirinə çevirə bilmərik. Beləliklə, cavabı belə yazırıq "Mümkün deyil".

Dəyişdirildikdən sonra ən kiçik palindrom üçün alqoritm

1. Nöqtə simvollarını nəzərə almadan cüt nöqtəli simvolları yoxlayın.

•  Sol və sağ hər ikisi nöqtə deyilsə və bərabər deyilsə, False qaytarın.
• Başqa, ortaya qədər keçin.
• Doğru qayıdın, sona çatsa.

2. Hər iki 'i' və 'ni-1' mövqeləri nöqtələrdirsə, onları 'a' ilə əvəzləyin.

3. Başqa bir şey, bunlardan biri nöqtəli bir xarakterdirsə, onu başqa bir nöqtə olmayan simvolla əvəz edin.

4. Son simli qaytarın.

Həyata keçirilməsi

Dəyişdirildikdən Sonra Ən Kiçik Palindrom üçün C ++ proqramı

#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;
}

Dəyişdirildikdən Sonra Ən Kiçik Palindrom üçün Java proqramı

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

Dəyişdirildikdən Sonra Ən Kiçik Palindrom üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (n) hara n verilən sətrin ölçüsüdür "S". Burada yalnız verilən simli keçib bir neçə faydalı tapşırıq yerinə yetiririk.

Kosmik Mürəkkəblik

O (1) çünki burada əlavə yerdən istifadə etmirik. Bizi daimi kosmik mürəkkəbliyə aparır.