HackerEarth String Restoration problem solution

In this HackerEarth String Restoration problem solution, Alice was given a string S. She made a prefix array P out of it. The value of prefix array i.e. P[i] is the count of distinct characters in the substring of string S from position 0 to i. Since the string is lost, you need to print a string that satisfies this prefix array.

If there is more than one correct answer, print the lexicographically smallest of them. If there is no such string then you need to print -1.

HackerEarth String Restoration problem solution.

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){ a%=m;LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
int p[10001];
int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        int cur = 0;
        char temp = 'a';
        --temp;
        string ans;
        bool flag = 1;
        for(int i = 1; i <= n; i++) {
            cin >> p[i];
            if(p[i] == 0)
                flag = 0;
            if(p[i] != p[i - 1]) {
                ++cur;
                if(cur > 26) {
                    flag = 0;
                }
                else {
                    ++temp;
                }
            }
            if(flag == 1 && cur != p[i]) {
                flag = 0;
            }
            else {
                ans.push_back(temp);
            }
        }
        if(flag) {
            cout << ans << endl;
        }
        else {
            cout << -1 << endl;
        }
    }    
}

HackerEarth String Restoration problem solution.

Leave a Reply