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
  • Apply
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Strings
  4. Common Child
  5. Discussions

Common Child

Problem
Submissions
Leaderboard
Discussions
Editorial
Topics

Sort 649 Discussions, By:

recency

Please Login in order to post a comment

  • aayushguptap1
    1 week ago+ 0 comments

    Standard Longest Common Subsequence Problem: Answer is length of LCS

    int commonChild(string s1, string s2)
    {
        int m = s1.length();
        int n = s2.length();
        
        vector<int> curr(n+1,0), prev(n+1,0);
        
        for(int i=1;i<=m;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if(s1[i-1] == s2[j-1])
                curr[j] = 1 + prev[j-1];
                else
                 curr[j] = max(curr[j-1],prev[j]);
            }
            prev = curr;
        }
        return curr[n];
    }
    
    0|
    Permalink
  • panbinwot
    4 weeks ago+ 0 comments

    Python I formed it as standard DP problem. Using fill-in-the-maxtrix to solve it. 1st of all, my solution below:

    def commonChild(s1, s2):
        arr = [[0 for _ in range(len(s1)+1)] for _ in range(len(s2)+1) ]
        for i in range(1,len(s1)+1,1):
            for j in range(1,len(s2)+1,1):
                arr[i][j]=max(
                    ((arr[i-1][j-1] +1) if s1[i-1]==s2[j-1] else arr[i-1][j-1]),
                    arr[i-1][j],
                    arr[i][j-1]
                )
        return arr[-1][-1] 
    
    1|
    Permalink
  • shin202
    2 months ago+ 0 comments

    Typescript Solution

    const commonChild = (s1: string, s2: string): number => {
        const m = s1.length;
        const n = s2.length;
    
        // @ts-ignore
        const matrix: number[][] = Array.from({length: m + 1}, () => Array(n + 1).fill(0));
    
        let longestChild = matrix[0][0];
    
        for (let i = 1; i <= m; i++) {
            for (let j = 1; j <= n; j++) {
                if (s1[i - 1] === s2[j - 1]) {
                    matrix[i][j] = matrix[i - 1][j - 1] + 1;
                } else {
                    matrix[i][j] = Math.max(matrix[i - 1][j], matrix[i][j - 1]);
                }
    
                if (matrix[i][j] > longestChild) {
                    longestChild = matrix[i][j];
                }
            }
        }
    
        return longestChild;
    }
    
    0|
    Permalink
  • adityayv0001
    2 months ago+ 1 comment
    def commonChild(s1, s2):
        # Write your code here
        prev=[-1 for i in range(len(s2)+1)]
        for i in range(len(s1),-1,-1):
            curr=[-1 for i in range(len(s2)+1)]
            for j in range(len(s2),-1,-1):
                if i==len(s1) or j==len(s2):
                    curr[j] = 0
                else:
                    if s1[i]==s2[j]:
                        curr[j] = 1+prev[j+1]
                    else:
                        curr[j] = max(prev[j],curr[j+1])
            prev=curr
        return curr[0]
    
    1|
    Permalink
  • shushant_20_21s1
    4 months ago+ 0 comments

    longest common subsquence with tabulation

    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