CAKP03 - Editorial

editorial
,
1

PROBLEM LINK:

Chef and 2 Strings

Author: Nikeshsingh Baghel

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM:

Chef used to think of a word and compare that word with a random word generated by computer. Then he tries to generate the word he thought by deleting several characters (0 or more) from the word generated by computer.

You are given 2 strings - Chef’s word and computer generated word. You need to check whether it is possible to reduce computer generated word to Chef’s word by deleting 0 or more characters.

QUICK EXPLANATION:

We have to find all the characters of Chef’s word in a sequence in the computer generated string.
Consider having a pointer which initially points towards the first character of Chef’s word and the pointer increments its value to point towards the second character only when first character is found.

Similarly find all the characters of Chef’s word in the second string by incrementing pointer.
If all the characters are found in the second string, then print the result as ‘YES; otherwise print the result as NO.

SOLUTION:

Setter's Solution 
def solve(t, s):
	n = len(s)

	last = -1
	ans = ''

	if s == t or t in s:
		return ("YES")

	for ch in t:
		try:
			c = s[last+1:].index(ch)
			ans += s[last+1+c]
			last += c + 1
		except:
			break

		if last == n-1:
			break

	if ans == t:
		return "YES"

	return "NO"

test = int(input())

for _ in range(test):
	chef = input()
	computer = input()
	print(solve(chef, computer))