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

Notebook file
https://github.com/lucaslouca/coding-problems/tree/master/python/Abbreviation