Permutasiyalarla ən uzun yayılmış sonrakı nəticə

Problem bəyanat

“Permutasiyalarla ən uzun yayılmış sonrakı nəticə” problemində ikisini verdik strings "S" və "t". Yerləşdirmələri verilmiş iki sətrin alt ardıcıllığı olan ən uzun simli tapın. Çıxış ən uzun sıralanmalıdır.

Giriş Formatı

"S" simli olan ilk sətir.

"T" simli olan ikinci sətir.

Çıxış formatı

Birinci sətir yalnız ən uzun sətri təmsil edən bir simli ehtiva edir dəyişmələr "s" və "t" simlərinin alt ardıcıllığıdır.

misal

hello
hole

ehlo

Explanation: Burada “ehlo” nun əvəzlənməsi sonradan salam, bütün mümkün permutations arasında sıralanmış və ən uzun olan çuxur.

Alqoritm

1. Count1 və count2 iki massiv yaradın.

2. Count1 simvol sayını string1-də, count2 simvol sayını string2-də saxlayır.

3. Nəticəyə 'c' simvolunu min (count1 ['c'], count2 ['c']) dəfə əlavə edin.

4. Bütün simvollar üçün bunu leksikoqrafik qaydada edin.

5. Son nəticəni qaytarın.

Həyata keçirilməsi

Permutasiyalarla ən uzun ümumi nəticəni tapmaq üçün C ++ proqramı

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    string s,t;
    cin>>s>>t;
    int count1[26] = {0};
    int count2[26] = {0};
    for (int i=0; i<s.length(); i++)
    {
        count1[s[i]-'a']++;
    }
    for (int i=0; i<t.length(); i++)
    {
        count2[t[i]-'a']++;
    }
    string ans;
    for(int i=0; i<26; i++)
    {
        for (int j=1;j<=min(count1[i],count2[i]); j++)
        {
            ans.push_back('a' + i);
        }
    }
    cout<<ans<<endl;
    return 0;
}

Permutasiyalarla Ən Uzun Ortaq Nəticəni tapmaq üçü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();
        String t = sr.next();
        int count1[] = new int[26];
        int count2[] = new int[26];
        for(int i=0;i<26;i++)
        {
            count1[i]=0;
            count2[i]=0;
        }
        for (int i=0; i<s.length(); i++)
        {
            count1[s.charAt(i)-'a']++;
        }
        for (int i=0; i<t.length(); i++)
        {
            count2[t.charAt(i)-'a']++;
        }
        String ans="";
        for(int i=0; i<26; i++)
        {
            for (int j=1;j<=Math.min(count1[i],count2[i]); j++)
            {
                ans+=(char)('a' + i);
            }
        }
        System.out.println(ans);
    }
}

tutorialcup
algorithm

ailort

Permutasiyalarla ən uzun ümumi nəticəni tapmaq üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n) hara n “s” və “t” arasında maksimum ölçülü sətrin uzunluğunu göstərir.

Kosmik Mürəkkəblik

O (n) çünki son cavabı simdə saxlayırıq. Və hər iki simli bərabərdirsə, simlin maksimum uzunluğu n-ə bərabərdir.