Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.For example, "ace" is a subsequence of "abcde".A common subsequence of two strings is a subsequence that is common to both strings. Example 1:Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3.
Question
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.For example, "ace" is a subsequence of "abcde".A common subsequence of two strings is a subsequence that is common to both strings. Example 1:Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3.
Solution
Sure, I can help with that. This problem can be solved using dynamic programming. Here is a step-by-step solution in Python:
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
if text1[i] == text2[j]:
dp[i][j] = dp[i + 1][j + 1] + 1
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])
return dp[0][0]
Here's how it
Similar Questions
Given a pair of strings of equal lengths, Geek wants to find the better string. The better string is the string having more number of distinct subsequences. If both the strings have equal count of distinct subsequence then return str1.Example 1:Input:str1 = "gfg", str2 = "ggg"Output: "gfg"Explanation: "gfg" have 7 distinct subsequences whereas "ggg" have 4 distinct subsequences. Example 2:Input: str1 = "a", str2 = "b"Output: "a"Explanation: Both the strings have only 1 distinct subsequence. Your Task:You don't need to read input or print anything. Your task is to complete the function betterString() which takes str1 and str2 as input parameters and returns the better string.Expected Time Complexity: O( max( str1.length, str2.length ) )Expected Auxiliary Space: O( max( str1.length, str2.length ) )Constraints:1 <= str1.lenght , str2.length <= 30
Given 2 strings A and B, check if A is present as a subsequence in B.
Strings - Longest Common PrefixGiven the array of strings A, you need to find the longest common string S which is the prefix of all the strings present in the array.For example, you are given an array of two strings S1 and S2.S1 = "abcdefgh"S2 = "abcefgh"Longest common prefix of S1 and S2 is "abc"Note: Assume that there always exists some common prefix among the stringsConstraints:0 <= length of array <= 104Input Format:First line of input contains an integer N representing the size of the arrayNext N lines contains strings of the array A, each in a line.Output Format:Print the longest common prefix of all strings of ASample Test CasesTest Case 1:Expected Output:5programmerprogrammingprogramprogramaticprogramableprogramTest Case 2:Expected Output:4appleapplepieapple tree apple phoneapple
You are given an array of strings arr. A string s is formed by the concatenation of a subsequence of arr that has unique characters.Return the maximum possible length of s.A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements. Example 1:Input: arr = ["un","iq","ue"]Output: 4Explanation: All the valid concatenations are:- ""- "un"- "iq"- "ue"- "uniq" ("un" + "iq")- "ique" ("iq" + "ue")Maximum length is 4.
Given a string s of length n, find all the possible subsequences of the string s in lexicographically-sorted order.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.