Solution 3 for Scaler Topics Fortnightly Contest - 2

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

Build an AI-First Career, Master the Complete Skillset

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

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

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation