SPPSTR - Editorial

PROBLEM LINK:

Practice
Div-2 Contest

Author: Vishal Anand
Testers: Swapnil Rustagi, Smit Mandavia
Editorialist: Vishal Anand

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

String, DP

PROBLEM:

Given two strings A and B where A consists of lowercase english alphabets while B can contain lowercase english alphabets and also three more special characters #, ? and !. Each of these special characters are associated with some lowercase english alphabets. Each of these special characters occurrences in the string B can either be dropped or can be replaced by any of their respective associated english lowercase characters any number of times and in any order. The task is to tell the minimum number of distinct special characters used to convert the string B into A. If not possible then print -1.

QUICK EXPLANATION:

Since we need to tell the minimum number of distinct special characters used, if the string B is convertible into A, then the answer will lie between 0 to 3 (both inclusive) i.e. we drop all the special characters in B or we use all the three different types of special characters. Therefore, there will be a total of 8 possibilities (2^3) of dropping or not dropping a particular special character. For each of these 8 possibilities, we write a 2D DP table for pattern matching to find if the string B, containing those particular submasks of special characters, is matched with the string A. The answer is the minimum number of distinct special characters used for which the string B matches to the string A.

EXPLANATION:

There are three types of special characters #, ? and !. The problem boils down to first solve using only one type of special character. Then we have a string A which has to be formed from string B where B contains only one type of special character. We’ll now check whether the string B is convertible to A.

This one can be solved using pattern matching dynamic programming where we build a 2-D DP table dp[N][M] where N is the length of the string A and M is the length of the string B which contains only one type of special character. Now, we can define the state dp[i][j] = true if A[i,...N] can be formed from B[j,...M] else dp[i][j] = false. The table can be filled using the logic:

  1. dp[i][j] = dp[i + 1, j + 1] | dp[i + 1, j] | dp[i, j + 1] if B[j] is a special character and A[i] is associated with B[j]

  2. dp[i][j] = dp[i, j + 1] if B[j] is a special character but A[i] is NOT associated with B[j]

  3. dp[i][j] = dp[i + 1, j + 1] if B[j] is not a special character and A[i] = B[j]

For the case 1) when B[j] is a special character which associates with A[i], there are three paths for us.

  • dp[i][j] = dp[i + 1][j + 1], We match the B[j] only with A[i] i.e one time
  • dp[i][j] = dp[i + 1][j], We match B[j] with A[i] but also try to match B[j,...M] with A[i + 1,...N] too
  • dp[i][j] = dp[i][j + 1], We just drop B[j] and try to match A[i,...N] with B[j + 1,...M]

For the case 2) we can simply drop the B[j] and try to match A[i,…N] with B[j + 1,...M].

For the case 3) we must have to match A[i] and B[j], therefore then try to match A[i + 1,...N] with B[j + 1,...M].

Now, given one type of special character in the string B we can build this dp table to find if A can be formed from B or not. Now, in the problem we are given 3 types of special characters #, ? and !. We can either include or not include a particular type of special character for our final answer. So, we’ll find all permutations of whether to take or not take a particular type of special character (2^3 = 8). For each submask, we’ll calculate the dp table but taking the set of special characters instead of just one special character while considering this submask. The answer will be the minimum number of special characters considered while making the dp table whose dp[0][0] is true. If none such dp[0][0] = true exists, then the answer will be -1 means A cannot be formed from B using any combinations.

Time Complexity:

Building a single DP table will take O(N * M), where N and M are the lengths of the strings A and B respectively. We build the DP tables for all the submasks of special characters, so O(2^{all\_distinct\_special\_characters} * N * M). Here the all\_distinct\_special\_characters is 3. There are T test cases so final time complexity of the solution is O(T * 2^{number of special characters} * N * M).

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 607;
string A, B;
set<char> has[8];
int dp[MAX][MAX];
 
int spToNum(char a) {
	if(a == '#')	return 1;
	if(a == '?')	return 2;
	else 	return 4;
}
 
int solve(int l, int r, const int sp) {
	int n = A.length(), m = B.length();
	if(l == n && r == m)	return 1;
	if(l != n && r == m)	return 0;
	if(dp[l][r] != -1)	return dp[l][r];
	if(l == n && r != m) {
		if(B[r] == '#' || B[r] == '?' || B[r] == '!')
			return dp[l][r] = solve(l, r + 1, sp);
		return dp[l][r] = 0;
	}
	int ret;
	if(B[r] == '#' || B[r] == '?' || B[r] == '!') {
		int x = spToNum(B[r]);
		if((sp & x) && has[x].find(A[l]) != has[x].end()) {
			ret = solve(l + 1, r + 1, sp) | solve(l + 1, r, sp) | solve(l, r + 1, sp);
		} else {
			ret = solve(l, r + 1, sp);
		}
	}
	else {
		if(A[l] == B[r])	ret = solve(l + 1, r + 1, sp);
		else 	ret = 0;
	}
	return dp[l][r] = ret;
}
 
int main(){
 
	int t;
	cin >> t;
	while(t--) {
		int ans = 10;
		cin >> A >> B;
		has[1].clear();
		has[2].clear();
		has[4].clear();
		for(int i = 1; i <= 4; i <<= 1) {
			string asch;
			cin >> asch;
			for(int j = 0; j < asch.length(); j++) {
				has[i].insert(asch[j]);
			}
		}
		for(int i = 0; i < 8; i++) {
			for(int j = 0; j < MAX; j++) {
				for(int k = 0; k < MAX; k++) {
					dp[j][k] = -1;
				}
			}
			if(solve(0, 0, i) == 1)
				ans = min(ans, __builtin_popcount(i));
		}
		cout << (ans == 10 ? -1: ans) << endl;
	}
 
	return 0;
}
2 Likes