I was reviewing my solution for this problem.
The algorithm simply has two pointers and compares each string given the subset of the characters. For each pointer and for a given query if a character is not in the string it advances the pointer past it, otherwise it checks to see if the two pointers point at the same character, in which case it advances both of them. If both conditions fail, it simply breaks out of the loop and prints “N”.
The algorithm has a time complexity of O(Q * (|s| + |t| + size of alphabet)) which should perform around 10^10 operations which is clearly much too slow, but in randomly generated strings, the break condition saves it from going through the both strings most of the time. However, one could probably force it to fail by putting a long run of the same character at the start of each string (or even just making a majority of the answers “Y”), but surprisingly nothing of the sort is present in the given test cases, hence it passes all of them.
Java code below:
import java.io.*;
import java.util.*;
public class Subset {
public static void main(String[] args) throws IOException {
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);
String a = r.readLine();
String b = r.readLine();
int querries = Integer.parseInt(r.readLine());
for(int i=0; i<querries; i++)
{
String h=r.readLine();
boolean[] letters = new boolean[18];
for(int j=0; j<h.length(); j++)
letters[h.charAt(j)-'a']=true;
int pointer1=0;
int pointer2=0;
while(pointer1<a.length()&&pointer2<b.length())
{
if(a.charAt(pointer1)==b.charAt(pointer2))
{
pointer1++;
pointer2++;
}
else if(!letters[a.charAt(pointer1)-'a'])
pointer1++;
else if(!letters[b.charAt(pointer2)-'a'])
pointer2++;
else
break;
}
if(pointer1==a.length()&&pointer2==b.length())
pw.print("Y");
else
{
while(pointer1<a.length()&&!letters[a.charAt(pointer1)-'a'])
pointer1++;
while(pointer2<b.length()&&!letters[b.charAt(pointer2)-'a'])
pointer2++;
if(pointer1==a.length()&&pointer2==b.length())
pw.print("Y");
else
pw.print("N");
}
}
pw.close();
}
}
Unfortunately, in contest I had miss typed a variable name and didn’t manage to find it in time resulting in only half credit for my solution (which this brute force probably doesn’t even deserve), resulting in getting a score above the cutoff threshold but below the threshold for an icp.