Ən uzun Palindrom, Simvolların Silinməsi və ya Yenidən Düzəldilməsi ilə Yarana bilər

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon Çatdırılma InfoEdge UHG Optum
Sükut Hashing Palindrom SimBaxılıb 382

Problem bəyanat

“Ən uzun Palindrom Xarakterlərin Silinməsi və ya Yenidən Düzəldilməsi Ola bilər” problemində sim "S". Ən uzununu tapın palindrom bəzi simvolları və ya sıfır simvolları sətirdən çıxarmaq və ya yenidən düzəltməklə qurula bilər. Mümkün bir çox həll ola bilər, onlardan hər hansı birini çap edə bilərsiniz.

Giriş Formatı

"S" simli olan ilk və yalnız bir sətir.

Çıxış formatı

Simvolunu təmsil edən bir simli çap edin Ən uzun Palindrom "s" simvolunun Silinməsi və ya Yenidən Düzəldilməsi ilə Yaranan.

Məhdudiyyətlər

  • 1 <= | s | <= 10 ^ 6
  • s [i] kiçik İngilis əlifbası olmalıdır

misal

abc
a

Explanation: Burada a-nın sayı 1-ə, b-nin sayı 1-ə, c-nin sayı da 1-ə bərabərdir. Beləliklə, burada “a”, “b” və ya “c” olan 3 cavab mümkündür.

aabb
abba

Explanation: Burada a-nın sayı 2-yə, b-nin sayı-2-yə bərabərdir. Beləliklə, başlanğıcımızda “ab”, ortası sıfır, sonu “ba” olur. Beləliklə, son cavabımız “abba” olacaqdır.

Alqoritm

Palindromun üç hissəsi olsun → başlanğıc, orta, son Orta bir simvol və ya boş olmalıdır, sonu başlanğıcın tərsidir. Və ölçülü sətir 2n + 1 və ya 2n-dir.

1. Əvvəlcə bir freq [] massivi elan edin bütün dəyərlər 0 və bütöv bir bayraq = 0 ilə başlanğıc edilir.

2. Tezlik [] massivində simvolların tezliyini və ya sayını saxlayın.

3. Hər bir 'a' - 'z' simvollarını ziyarət etmək üçün sadəcə bir döngə işlədin.

4. Bir simvolun sayı tək və bayraq dəyəri sıfır olarsa. Bu xalı ortada edirik. Və başlanğıcda bu işarəni tez-tez [ch] / 2 dəfə əlavə edin.

5. Başqa birinə başlanğıcın sonunda cari char frekansı [ch] / 2 dəfə əlavə edin.

6. Başlanmanın tərs hissəsi bizim sonumuz olacaq.

7. Beləliklə, son cavabımız başlanğıcın, ortanın, sonun birləşməsi olacaq.

Həyata keçirilməsi

C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;

int main()
{
   string s;
   cin>>s;
   int n=s.length();
   int freq[26]={0};
   for(int i=0;i<n;i++)
   {
       freq[s[i]-'a']++;
   }
   string start="",mid="", end=""; 
   int flag=0;
   for(int i=0;i<26;i++)
   {
       if(freq[i]%2==1 && flag==0)
       {
           flag=1;
           mid+= ('a'+i);
           for(int j=0;j<freq[i]/2;j++)
           {
               start+=('a'+i);
           }
       }
       else
       {
           for(int j=0;j<freq[i]/2;j++)
           {
               start+=('a'+i);
           }
       }
   }
   end = start;
   reverse(end.begin(), end.end());
   string ans="";
   ans+=start;
   ans+=mid;
   ans+=end;
   cout<<ans<<endl;
   return 0;
}

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();
        int freq[] = new int[26]; 
        for(int i=0;i<26;i++) 
        {
            freq[i]=0; 
        }
        for(int i=0;i<n;i++) 
        {
            freq[s.charAt(i)-'a']++; 
        }
        String start="",mid="", end=""; 
        int flag=0;
        for(int i=0;i<26;i++)
        {
            if(freq[i]%2==1 && flag==0)
            {
                flag=1;
                char ch = (char)('a'+i);
                mid+=ch;
                for(int j=0;j<freq[i]/2;j++)
                {
                    start+=ch;   
                }
            }
            else
            {
                for(int j=0;j<freq[i]/2;j++)
                {
                    char ch = (char) ('a'+i);
                    start+=ch;
                }
            }
        }
        end = start;
        StringBuilder temp = new StringBuilder(end);  
        temp.reverse();
        String ans="";
        ans+=start;
        ans+=mid;
        ans+=temp;
        System.out.println(ans);
    }
}




duvwedcvhwwecv
cdevwhwvedc

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) hara n verilən sətrin ölçüsüdür "S". Burada sadəcə “s” simvolunda olan hər bir xarakterin tezliyini saxlayırıq. Xətti vaxta uyğun olaraq bəzi əməliyyatlar aparın və cavabı alın.

Kosmik Mürəkkəblik

O (n) çünki son cavabı saxlamalıyıq. Və son sətrin maksimum uzunluğu verilən sətrə bərabər olacaqdır.

Translate »