Complete The Word – Codeforces 716B (Div. 2)

ABC??FGHIJK???OPQR?TUVWXY?

ABCDEFGHIJKLMNOPQRZTUVWXYS

WELCOMETOCODEFORCESROUNDTHREEHUNDREDANDSEVENTYTWO

-1

??????????????????????????

MNBVCXZLKJHGFDSAQPWOEIRUYT

AABCDEFGHIJKLMNOPQRSTUVW??M

-1

2. Ý tưởng giải quyết

• Đầu tiên bạn tạo mảng 1 chiều lưu lại số lần xuất hiện của kí tự trong xâu con a[0]->a[25]
• sau đó bạn đếm xem có bao nhiêu chữ cái trong đó xuất hiện trên 1 lần. (đặt tên là biến dem)
• sau đó bạn dựa vào dem để tính, và xác định xem đoạn con đó có khả năng là xâu con đẹp ko? nếu không thì bạn cứ tịnh tiến cái phạm vi thống kê số lần xuất hiện dần hết xâu a đồng thời cập nhật biến dem, nếu chỗ nào thỏa mãn (dem==0) thì bạn xử lí thôi.

Nhận xét: nếu độ dài xâu a < 26 -> không tồn tại

Độ phức tạp O(|s|)

3. Code Codeforces 716B

#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;

char a[50001];
long dd[50001],leng;

void xuli()
{
    long i,j,dem=0;
    //init
    for (i=0; i<=25; i++)
        dd[i]=0;
    //exit
    if (leng<26)
    {
        cout << "-1"<<endl;
        return;
    }
    // tinh trc
    for (i=0; i<=25; i++)
        if (a[i]!='?')
            dd[a[i]-65]++;
    //update dem
    for (i=0; i<=25; i++)
        if (dd[i]>1)
            dem++;

    for (i=0; i<=leng-26; i++)
    {
        if ( (a[i-1]!='?') && (i!=0))
        {
            if (dd[a[i-1]-65]==2)
                dem--;
            dd[a[i-1]-65]--;
        }
        if ( (a[i+25]!='?') && (i!=0))
        {
            if (dd[a[i+25]-65]==1)
                dem++;
            dd[a[i+25]-65]++;
        }
        if (dem==0)
        {
            long k=0;
            for (j=0; j<=i-1; j++)
                if (a[j]!='?')
                    cout <<a[j];
                else
                    cout << "A";

            for (j=i; j<=i+25; j++)
                if (a[j]!='?')
                    cout <<a[j];
                else
                {
                    while (dd[k]>0)
                        k++;
                        cout << (char)(k+65);
                    k++;
                }

            for (j=i+25+1; j<=leng-1; j++)
                if (a[j]!='?')
                    cout <<a[j];
                else
                    cout <<"A";
            cout << endl;
            return;
        }
    }
    cout << "-1"<<endl;
}

int main()
{
    cin>>a;
    leng=strlen(a);
    xuli();
    return 0;
}