## fizzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Abbreviation challenge

Sharing is caring!

Problem statement
You can perform the following operation on some string, $a$:
1. Capitalize zero or more of $a$‘s lowercase letters at some index i (i.e., make them uppercase).
2. Delete all of the remaining lowercase letters in $a$.

Given $q$ queries in the form of two strings, $a$ and $b$, determine if it’s possible to make $a$
equal to $b$ by performing the above operation on $a$. If $a$ can be transformed into $b$,
print `YES` on a new line; otherwise, print `NO`.

Input Format
The first line contains a single integer, $q$, denoting the number of queries. The $2q$ subsequent lines describe each query in the following format:
1. The first line of each query contains a single string, $a$.
2. The second line of each query contains a single string, $b$.

Constraints
$1\le q \le 10$
$1 \le |a|, |b| \le 1000$
String $a$ consists only of uppercase and lowercase English letters.
String $b$ consists only of uppercase English letters.

Output Format
For each query, print `YES` on a new line if it’s possible to make string $a$ equal to string $b$ by
performing the operation specified above; otherwise, print `NO`.

Sample Input

```1
daBcd
ABC
```

Sample Output

```YES
```

Explanation
We have $a = daBcd$ and $b = ABC$. We perform the following operation:
1. Capitalize the letters a and c in $a$ so that $a = dABCd$.
2. Delete all the remaining lowercase letters in $a$ so that $a = ABC$.

Because we were able to successfully convert $a$ to $b$, we print `YES` on a new line.

Solution

```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()
```