Solution 3 for Scaler Topics Fortnightly Contest - 2

This article is part of the Scaler Topics Fortnightly Contest - 2.

Solution Approach

• Let n be length of A, and m be the length of B.
• Let's say for an ith position in string A, L[i] is the largest integer such that string B0...L[i] is present as a subsequence in A0..i .
• Similarly, for ith position in string A, R[i] is the smallest integer such that string BR[i]...m-1 is present as a subsequence is Ai..n-1.
• Then for each i, if L[i] >= R[i] is true, then your answer is "Yes". Otherwise "No". So now, How to find L[i] and R[i]?
• For L[i] -
• Make a pos array of length 26 and initialize it to 0. Initialize integer j = 0, with which we will be iterating B.
• Where pos[i] will store the largest index where ith character of lowercase english letters exists. e.g 0th position is for character 'a'.
• Now start traversing string A. Whenever you find a match i.e. A[i] == B[j], do the following :
• update pos[A[i]-'a'] = j, increment j.
• For each i do the following L[i] = pos[A[i]-'a'].
• Similiarily you can do for R[i], but from back.

C++ Implementation

Java Implementation

Python Implementation