أصغر Palindrome بعد الاستبدال


مستوى الصعوبة سهل
كثيرا ما يطلب في أدوبي Arcesium Flipkart جنرال إلكتريك للرعاية الصحية ZScaler
الفرعية العكسية خيط

المشكلة بيان

في مشكلة "أصغر متناظرة بعد الاستبدال" قدمنا ​​المدخلات سلسلة يحتوي على أحرف أبجدية صغيرة ونقاط (.). نحتاج إلى استبدال جميع النقاط ببعض الأحرف الأبجدية بحيث تصبح السلسلة الناتجة متناظرة. ال سياق متناظر ينبغي أن تكون lexicographically أصغر.

نمط الإدخال

السطر الأول والوحيد الذي يحتوي على سلسلة الإدخال s.

تنسيق الإخراج

اطبع أصغر سلسلة معجمية وهي متناظرة اللون. إذا لم يتم تشكيل مثل هذه السلسلة ، فقم بالطباعة "غير ممكن".

القيود

  • 1 <= | ث | <= 10 ^ 6
  • s [i] هي أحرف أبجدية صغيرة أو نقطة "."

مثال

a..b.a
aabbaa

التفسير: بالنسبة لهذه السلسلة ، فإن أصغر متناظر هو "عباء". هنا نستبدل s [i] و s [n-1-i] بـ "a" إذا كان كلا الحرفين عبارة عن نقطة (.). إذا كان أحدهم حرفًا نقطيًا ، فاستبدله بحرف آخر غير نقطي.

a..b.c
Not possible

التفسير: في هذه السلسلة ، يمكننا أن نرى بسهولة أن الحرفين الأول والأخير ليسا متماثلين ، لذا لا يمكننا تحويل هذه السلسلة إلى سلسلة متناظرة. لذلك ، نقوم بطباعة الإجابة كـ "غير ممكن".

خوارزمية لأصغر Palindrome بعد الاستبدال

1. تحقق من زوج من الأحرف غير النقطية مع تجاهل الأحرف النقطية.

  •  إذا كان كل من اليسار واليمين غير متساويين وغير متساويين ، فقم بإرجاع خطأ.
  • عدا ذلك ، اجتياز حتى منتصف.
  • إرجاع صحيح ، إذا وصل إلى النهاية.

2. إذا كانت كلتا المواضع "i" و "ni-1" عبارة عن نقطتين ، فاستبدلهما بـ "a".

3. عدا ذلك ، إذا كان أحدهم حرفًا نقطيًا ، فاستبدله بحرف آخر غير نقطي.

4. أعد السلسلة النهائية.

تطبيق

برنامج C ++ لأصغر 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;
}

برنامج Java لأصغر 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

تحليل التعقيد لأصغر متناظرة بعد الاستبدال

تعقيد الوقت

O (ن) أين n هو حجم السلسلة المحددة "س". هنا نقوم فقط باجتياز السلسلة المحددة ونقوم ببعض المهام المفيدة.

تعقيد الفضاء

يا (1) لأننا لا نستخدم أي مساحة إضافية هنا. الأمر الذي يقودنا إلى التعقيد المكاني المستمر.