You can perform the following operation on some string, :
1. Capitalize zero or more of ‘s lowercase letters at some index i (i.e., make them uppercase).
2. Delete all of the remaining lowercase letters in .
Given queries in the form of two strings, and , determine if it’s possible to make
equal to by performing the above operation on . If can be transformed into ,
YES on a new line; otherwise, print
The first line contains a single integer, , denoting the number of queries. The subsequent lines describe each query in the following format:
1. The first line of each query contains a single string, .
2. The second line of each query contains a single string, .
String consists only of uppercase and lowercase English letters.
String consists only of uppercase English letters.
For each query, print
YES on a new line if it’s possible to make string equal to string by
performing the operation specified above; otherwise, print
1 daBcd ABC
We have and . We perform the following operation:
1. Capitalize the letters a and c in so that .
2. Delete all the remaining lowercase letters in so that .
Because we were able to successfully convert to , we print
YES on a new line.
import sys def solve(a,b): if len(b) > len(a): print("NO") else: i = 0 # index for a j = 0 # index for b n = len(a) dp = [False for x in range(len(b))] while i < n: found = False while i < n and a[i].upper() != b[j]: if a[i].isupper() and b[j-1] != a[i]: print("NO") return i = i + 1 if i < len(a): found = True if found: dp[j] = True j = j + 1 if j == len(b): break i = i + 1 if dp[-1]: # Check if all a's remaining characters are lowercase # (because we can only delete remaining lowercase chars) for c in a[i+1:]: if c.isupper() and b[j-1] != c: print("NO") return print("YES") else: print("NO") def main(): f = open("in5.txt") queries = int(f.readline()) for q in range(0, queries): a = f.readline().strip() b = f.readline().strip() solve(list(a),list(b)) main()