Statement

Given two strings, str1 and str2, find the length of the shortest string that has both the input strings as subsequences.

Note: A string XX is a subsequence of string YY if deleting some number of characters from YY results in the string XX.

Let’s assume that we have two strings as follows:

  • str1 = "yabc"
  • str2 = "xabc"

There can be multiple strings that have str1 and str2 as subsequences, for example, "xyaabcc" and "xyabbc", but the shortest string that has these input strings as subsequences is "xyabc". Please note that the sequence of alphabets in the string can be altered.

Constraints:

  • 11 \leq str1.length, str2.length 3000\leq 3000
  • str1 and str2 consist of lowercase English letters.

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.