Need intuition for Educational Codeforces Round 81 (Problem C)

Problem link : Problem - C - Codeforces

I suppose we can use DP here, but I couldn’t figure out how. A brief explanation with solution would do it for me. TIA.

I solved it using Binary Search. Store all characters with their index in a vector…its like you first check the first character in string t, then jump to the first index of that character in string s, then move to next character in string t…then check the index of that character in string s which is just greater than the last index

Here is my solution, hope you can understand

C++ Code
#include <bits/stdc++.h>
using namespace std;
#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    
    int t;
    cin >> t;

    while(t--){
        string s,t;

        cin >> s >> t;

        map<char,vector<int> > freq1,freq2;

        for(int i = 0 ; i < s.length() ; i++){

            freq1[s[i]].push_back(i);

        }

        for(int i = 0 ; i < t.length() ; i++){

            freq2[t[i]].push_back(i);

        }
        
        int res=0;
        int i=0;
 
        bool hoga=true;

        while( i < t.length() && hoga){ 

            if(freq1[t[i]].size()==0){

                hoga=false;
                break;

            }

            int j=freq1[t[i]][0];

            i++;
            
            while(j<s.length()){
                auto it = upper_bound(freq1[t[i]].begin(), freq1[t[i]].end(),j);

                if(it == freq1[t[i]].end()){

                    break;

                }else{

                    j=*it;
                    i++;

                }
            }

            res++;
        }

        if(!hoga){

            cout << -1 << endl;

        }else{

            cout << res << endl;

        }
    }
    return 0;
}
2 Likes

This hash table isn’t supposed to be for string t right? I think it should be freq2[t[i]].push_back(i); based on the loop

Yup… My bad😅 corrected

Actually it doesn’t even matter, as we’re not using it anywhere :rofl:

I made a N*26 array of string s where every [ i ][ j ] gives the next position of the ith character on or after the jth index. ( Implementation below )

After that we can easily traverse linearly extracting continuous substring as long as possible of string t that are subsequences of string s one by one in order, because we can only append a subsequence at last of the existing string.

how to check if a string is a subsequence of the other using the above 2D array , See -

Queries on subsequence of string - GeeksforGeeks

Here is my code to the above problem -