DCP-228: Substring and Subsequence Back to All Problems

Hard Divide and Conquer > Greedy

Given two strings A and B. You have to find and print the longest substring of A which is also a subsequence of B. If there are multiple longest substring you should print the lexicographically smallest one. If there is no such substring you should print a blank line. Strings will only contain small English alphabets. Input: ------ Input starts with an integer **T (1<=8)**, denoting the number of test cases. Each case contains two line of strings. The first line denotes string A, and the second line denotes string B. ```1 <= length(A) <= 5000``` ```1 <= length(B) <= 100000``` Output: ------- For each case of input, print a line with the longest substring of A which is also a subsequence of B. If there is no such string print a blank line. Sample Input ------------ 2 ab ba devskill devlopmentskill Sample Output ------------- a devskill

Problem Setter:

Ahmad Faiyaz

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 1.00
C++ 1.00
C++14 1.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats




# User Language Timing
01 sahedsohel Cpp14 0.03s
02 tariqiitju Cpp14 0.03s
03 Morass Cpp14 0.03s
04 seyedssz Cpp14 0.05s
05 Mahmudul_Tushar Cpp14 0.06s
06 skmonir Cpp14 0.06s
07 feodorv C 0.13s
08 mamun4122 Cpp14 0.27s
09 fsshakkhor Cpp14 0.27s
10 sayedgkm Cpp14 0.27s
11 alhelal_cse Cpp14 0.27s
12 Robbinb1993 Cpp14 0.29s
13 AlirezaNa Cpp14 0.87s

Your feedback is our precious!

Or call +88 02 9853138 for support