educative.io

Re: shortest common supersequence problem

Courses
,
#1

Re: “Given two strings, write a function to find the length of their shortest common superstring. A superstring is a string that has both input strings as substrings”,

since in the example output, abdcf, s1 is not a substring of it, my question is around language. Doesn’t “substring” (in your definition of superstring) imply contiguity - which is not part of the requirement based upon the example output?

Course: https://www.educative.io/collection/10370001/5347133077061632
Lesson: https://www.educative.io/collection/page/10370001/5347133077061632/5796938106535936

#2

Hi @Nilay_Jhaveri !!
Yes, the definition of “substring” typically implies contiguity, meaning that a substring is a portion of a string that appears consecutively within that string. In the context of this problem statement, the goal is to find the shortest common superstring, the requirement is indeed different.

A superstring in this context does not necessarily imply contiguity. Instead, it means that the resulting string should contain both input strings as substrings, but there can be additional characters between them. This allows for non-contiguous combinations of the input strings to form the superstring.

So, in the example
Input:

string s1 = "abcf";string s2 = "bdcf";

Sample output

 The SCS is "abdcf"

although “s1” is not contiguous within the superstring, it is still considered a superstring because it contains both “s1” and “s2” as substrings, which is the primary requirement for a superstring in this problem.

To clarify, a superstring in this problem can include characters that are not part of either input string as long as it contains both input strings as substrings.
I hope it helps. Happy Learning :blush:

#3

Hi Javeria, my point was that for the superstring “abdcf”, “s1” is not a substring within it because it is not contiguously present within the superstring. So, was confused about the use of the language “substring” in this context.

#4

@Nilay_Jhaveri

  • A substring typically implies contiguity, meaning it consists of consecutive characters within the string.
  • A superstring is a string that contains other strings as substrings, and it doesn’t necessarily require those substrings to be contiguous.

So, in the example:

  • s1 = "abcf"
  • s2 = "bdcf"

The string “abdcf” is indeed a superstring of both s1 and s2 because it contains both “abcf” and “bdcf” as substrings, even though these substrings are not contiguous within “abdcf.”
So, “abdcf” contains both “abcf” and “bdcf” as substrings, making it a superstring of both s1 and s2.

1 Like
#5

Thank you, Javeria.

You say that [“abdcf” contains both “abcf” and “bdcf” as substrings].

How is abcf a substring of abdcf?

I don’t see abcf contiguously present within abdcf.

Can you clarify this point, specifically, for me? That’s the part that I’m stuck on.

#6

“abcf” and “bdcf” are subsequences of “abdcf”, not substrings of “abdcf”.

#7

“bdcf” is a substring of “abdcf”, but “abcf” is a subsequence of “abdcf”.

#8

Since substrings are also subsequences, this can be generalized to “abcf” and “bdcf” are subsequences of “abdcf”so that it holds true for all possible inputs.

1 Like