We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. LCS Returns
  5. Discussions

LCS Returns

Sort by

recency

|

24 Discussions

|

  • dehaka
     + 0 comments

    quadratic time O(A.size() * B.size())

    int LCSReturns(const string& A, const string& B) {
    int total = 0;
    vector<vector<int>> cache(A.size() + 1, vector<int>(B.size() + 1)), reverse(A.size() + 2, vector<int>(B.size() + 2));
    vector<vector<bool>> insertion(A.size() + 2, vector<bool>(75));
    for (int i = 1; i <= A.size(); i++) {
        for (int j = 1; j <= B.size(); j++) {
            if (A[i - 1] == B[j - 1]) cache[i][j] = cache[i - 1][j - 1] + 1;
            else cache[i][j] = max(cache[i - 1][j], cache[i][j - 1]);
        }
    }
    for (int i = A.size(); i >= 1; i--) {
        for (int j = B.size(); j >= 1; j--) {
            if (A[i - 1] == B[j - 1]) reverse[i][j] = reverse[i + 1][j + 1] + 1;
            else reverse[i][j] = max(reverse[i + 1][j], reverse[i][j + 1]);
        }
    }
    for (int i = 1; i <= A.size() + 1; i++) {
        for (int j = 1; j <= B.size(); j++) {
            if (insertion[i][B[j - 1] - '0']) continue;
            if (cache[i - 1][j - 1] + reverse[i][j + 1] == cache[A.size()][B.size()]) {
                insertion[i][B[j - 1] - '0'] = true;
                total++;
            }
        }
    }
    return total;
}

  • yashparihar729
     + 0 comments

    Here is my solution in java, javascript, python, C ,C++, Csharp HackerRank LCS Returns Problem Solution

  • jmwang
     + 0 comments

    The following codes work by pypy 3

    na=len(a)
nb=len(b)
dp=[[0]*(nb+1) for _ in range(na+1)]
for i in range(na):
    for j in range(nb):
        if a[i]==b[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])

suff=[[0]*(nb+1) for _ in range(na+1)]
for i in range(na-1,-1,-1):
    for j in range(nb-1,-1,-1):
        if a[i]==b[j]:
            suff[i][j]=suff[i+1][j+1]+1
        else:
            suff[i][j]=max(suff[i+1][j],suff[i][j+1])

cur = dp[na][nb]      
ret = 0
for i in range(na+1):
    used=[False]*(256)

    for j in range(nb):
        if used[ord(b[j])]==True:
            continue
        now=dp[i][j]+ suff[i][j+1] + 1
        if now == cur+1:
            used[ord(b[j])]=True
            ret+=1
return ret

  • thecodingsoluti2
     + 0 comments

    Here is LCS Returns problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-LCS-return-problem-solution.html

  • vizzy205
     + 0 comments

    Can anyone help me in this?

    M=62
def func(c):
    if(c>='a' and c<='z'):
        return ord(c)-97
    if(c>='A' and c<='Z'):
        return ord(c)-65
    return ord(c)-48

def tutzkiAndLcs(a, b):
    n=len(a)
    m=len(b)
    dp=[]
    dpr=[]
    position=[[] for i in range(M)]
    for i in range(1,m+1,1):
        position[func(b[i-1])].append(i)
    for i in range(n+2):
        dp+=[[0]*(m+2)]
        dpr+=[[0]*(m+2)]
    
    for i in range(1,n+1):
        for j in range(1,m+1):
            if a[i-1]==b[j-1]:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])

            
    for i in range(n,0,-1):
        for j in range(m,0,-1):
            if(a[i-1]==b[j-1]):
                dpr[i][j]=1+dpr[i+1][j+1]
            else:
                dpr[i][j]=max(dpr[i+1][j],dpr[i][j+1])
                
    #print(position)
    #print(dp)
    #print(dpr)   
    
    ans = 0
    for i in range(0,n+1,1):
        for c in range(0,26,1):
            for j in range(0,len(position[c]),1):
                p=position[c][j]
                if(dp[i][p-1] + dpr[i+1][p+1] == dp[n][m]):
                    ans+=1
                    break
    print(ans)    
    return ans