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.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. LCS Returns
  5. Discussions

LCS Returns

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 22 Discussions, By:

recency

Please Login in order to post a comment

  • jmwang
    2 months ago+ 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
    
    0|
    Permalink
  • thecodingsoluti2
    4 months ago+ 0 comments

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

    0|
    Permalink
  • vizzy205
    9 months ago+ 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
    
    0|
    Permalink
  • mk_meden
    10 months ago+ 0 comments

    https://codeforces.com/blog/entry/103769#comment-921563

    explanation and code

    0|
    Permalink
  • aditosh007
    1 year ago+ 0 comments

    I had a tough time understanding the problem when I tried it back then, so I figured I'll make things simple and have just posted a simple and different way of explanation on the youtube. Feedbacks much much appreciated, thank you. Link is https://youtu.be/abFiUC-UF0c Its just HackerRank has been my home site for learning, & I am just looking for a feedback on if I was able to explain the problem well and thoroughly, thank you :)

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy