Solution 3 for Scaler Topics Fortnightly Contest

Transform Your Career

Choose from our industry-leading programs designed for career success

NSDC Certified

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

NSDC Certified

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

NSDC Certified

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

NSDC Certified

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

NSDC Certified

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

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.