\n\n# Please Upvote as it really motivates me \uD83C\uDD99\uD83C\uDD99\uD83C\uDD99\n\n# Intuition & Approach\n\n##### \u2022\tThe shortestCommonSupersequence method takes two strings s1 and s2 as input and returns their shortest common supersequence\n##### \u2022\tThe first finds the longest common subsequence (LCS) of s1 and s2 using the lcs helper method\n##### \u2022\tThe lcs method takes two strings s1 and s2 as input and returns their LCS\n##### \u2022\tIt uses dynamic programming to fill a 2D array dp where dp[i][j] represents the length of the LCS of the first i characters of s1 and the first j characters of s2\n##### \u2022 Then backtracks from the bottom right corner of the dp array to find the LCS\n##### \u2022\tThe shortestCommonSupersequence method then merges s1 and s2 with the LCS to create the shortest common supersequence\n##### \u2022\tIt uses a StringBuilder to build the merged string\n##### \u2022\tThe method iterates over the characters of the LCS and adds characters from s1 and s2 until the LCS character is found\n##### \u2022\tIt then adds the LCS character to the merged string\n##### \u2022\tAfter all the LCS characters have been added, the method adds any remaining characters from s1 and s2 to the merged string\n##### \u2022\tThe method returns the merged string as the shortest common supersequence\n##### \u2022\tThe approach is to find the LCS of the two input strings and then merge the strings with the LCS to create the shortest common supersequence\n##### \u2022\tThe use of dynamic programming to find the LCS allows for an efficient solution\n\n# Code\n```java []\npublic String shortestCommonSupersequence(String s1, String s2) {\n // find the LCS of s1 and s2\n char lcs[] = lcs(s1,s2).toCharArray();\n int i=0,j=0;\n StringBuilder sb = new StringBuilder();\n // merge s1 and s2 with the LCS\n for(char c:lcs){\n // add characters from s1 until the LCS character is found\n while(s1.charAt(i)!=c) sb.append(s1.charAt(i++));\n // add characters from s2 until the LCS character is found\n while(s2.charAt(j)!=c) sb.append(s2.charAt(j++));\n // add the LCS character\n sb.append(c);\n i++;\n j++;\n }\n // add any remaining characters from s1 and s2\n sb.append(s1.substring(i)).append(s2.substring(j));\n // return the merged string\n return sb.toString();\n}\n\n// helper method to find the LCS of two strings\nString lcs(String s1,String s2){\n int m = s1.length(),n=s2.length();\n int dp[][] = new int[m+1][n+1];\n // fill the dp array using dynamic programming\n for(int i=1;i<=m;i++){\n for(int j=1;j<=n;j++){\n if(s1.charAt(i-1)==s2.charAt(j-1)){\n dp[i][j]=1+dp[i-1][j-1];\n }else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);\n }\n }\n // backtrack from the bottom right corner of the dp array to find the LCS\n StringBuilder sb = new StringBuilder();\n int i=m,j=n;\n while(i>0 && j>0){\n if(s1.charAt(i-1)==s2.charAt(j-1)){\n sb.append(s1.charAt(i-1));\n i--;\n j--;\n }else if(dp[i-1][j]>dp[i][j-1]) i--;\n else j--;\n }\n // reverse the LCS string and return it\n return sb.reverse().toString();\n}\n```\n```c++ []\nclass Solution {\npublic:\n string shortestCommonSupersequence(string s1, string s2) {\n // find the LCS of s1 and s2\n string lcs = getLCS(s1, s2);\n int i = 0, j = 0;\n string result = "";\n // merge s1 and s2 with the LCS\n for (char c : lcs) {\n // add characters from s1 until the LCS character is found\n while (s1[i] != c) {\n result += s1[i];\n i++;\n }\n // add characters from s2 until the LCS character is found\n while (s2[j] != c) {\n result += s2[j];\n j++;\n }\n // add the LCS character\n result += c;\n i++;\n j++;\n }\n // add any remaining characters from s1 and s2\n result += s1.substr(i) + s2.substr(j);\n // return the merged string\n return result;\n }\n\n // helper method to find the LCS of two strings\n string getLCS(string s1, string s2) {\n int m = s1.length(), n = s2.length();\n vector> dp(m+1, vector(n+1));\n // fill the dp array using dynamic programming\n for (int i = 1; i <= m; i++) {\n for (int j = 1; j <= n; j++) {\n if (s1[i-1] == s2[j-1]) {\n dp[i][j] = 1 + dp[i-1][j-1];\n } else {\n dp[i][j] = max(dp[i-1][j], dp[i][j-1]);\n }\n }\n }\n // backtrack from the bottom right corner of the dp array to find the LCS\n string lcs = "";\n int i = m, j = n;\n while (i > 0 && j > 0) {\n if (s1[i-1] == s2[j-1]) {\n lcs = s1[i-1] + lcs;\n i--;\n j--;\n } else if (dp[i-1][j] > dp[i][j-1]) {\n i--;\n } else {\n j--;\n }\n }\n return lcs;\n }\n};\n```\n```python []\nclass Solution:\n def shortestCommonSupersequence(self, s1: str, s2: str) -> str:\n # find the LCS of s1 and s2\n lcs = self.getLCS(s1, s2)\n i, j = 0, 0\n result = ""\n # merge s1 and s2 with the LCS\n for c in lcs:\n # add characters from s1 until the LCS character is found\n while s1[i] != c:\n result += s1[i]\n i += 1\n # add characters from s2 until the LCS character is found\n while s2[j] != c:\n result += s2[j]\n j += 1\n # add the LCS character\n result += c\n i += 1\n j += 1\n # add any remaining characters from s1 and s2\n result += s1[i:] + s2[j:]\n # return the merged string\n return result\n\n # helper method to find the LCS of two strings\n def getLCS(self, s1: str, s2: str) -> str:\n m, n = len(s1), len(s2)\n dp = [[0] * (n+1) for _ in range(m+1)]\n # fill the dp array using dynamic programming\n for i in range(1, m+1):\n for j in range(1, n+1):\n if s1[i-1] == s2[j-1]:\n dp[i][j] = 1 + dp[i-1][j-1]\n else:\n dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n # backtrack from the bottom right corner of the dp array to find the LCS\n lcs = ""\n i, j = m, n\n while i > 0 and j > 0:\n if s1[i-1] == s2[j-1]:\n lcs = s1[i-1] + lcs\n i -= 1\n j -= 1\n elif dp[i-1][j] > dp[i][j-1]:\n i -= 1\n else:\n j -= 1\n return lcs\n```\n\n# Complexity\n- Time complexity:o(n2)\n\n\n- Space complexity:o(n)\n\n\n# optimal \n```java []\n public String shortestCommonSupersequence(String s1, String s2) {\n // find the LCS of s1 and s2\n int m = s1.length(),n=s2.length();\n int dp[][] = new int[m+1][n+1];\n // fill the dp array using dynamic programming\n for(int i=1;i<=m;i++){\n for(int j=1;j<=n;j++){\n if(s1.charAt(i-1)==s2.charAt(j-1)){\n dp[i][j]=1+dp[i-1][j-1];\n }else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);\n }\n }\n // backtrack from the bottom right corner of the dp array to find the LCS\n StringBuilder sb = new StringBuilder();\n int i=m,j=n;\n while(i>0 && j>0){\n if(s1.charAt(i-1)==s2.charAt(j-1)){\n sb.append(s1.charAt(i-1));\n i--;\n j--;\n }else if(dp[i-1][j]>dp[i][j-1]){//shrink s1\n sb.append(s1.charAt(i-1));\n i--;\n }else{\n sb.append(s2.charAt(j-1));\n j--;\n }\n }\n while(i>0){//remaing 1 element in s1\n sb.append(s1.charAt(i-1));\n i--;\n }\n while(j>0){\n sb.append(s2.charAt(j-1));\n j--;\n }\n // reverse the LCS string and return it\n return sb.reverse().toString();\n}\n```\n\n\n![BREUSELEE.webp](https://assets.leetcode.com/users/images/062630f0-ef80-4e74-abdb-302827b99235_1680054012.5054147.webp)\n![image.png](https://assets.leetcode.com/users/images/303fa18d-281d-49f0-87ef-1a018fc9a488_1681355186.0923774.png)\n\n\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\nThanks for visiting my solution.\uD83D\uDE0A Keep Learning\nPlease give my solution an upvote! \uD83D\uDC4D \uD83C\uDD99\uD83C\uDD99\uD83C\uDD99\nIt\'s a simple way to show your appreciation and\nkeep me motivated. Thank you! \uD83D\uDE0A

Shortest Common Supersequence

Problem Description

Problem Description

Answer Panel