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

Common Child

Problem
Submissions
Leaderboard
Discussions
Editorial
Topics

Sort 609 Discussions, By:

votes

Please Login in order to post a comment

  • Spatzist
    7 years ago+ 23 comments

    Relevant Wikipedia article: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

    A straightforward solution uses O(n^2) time and space. Optimizations can reduce both of these.

    221|
    Permalink
    View more Comments..
  • Tsukuyomi1
    5 years ago+ 18 comments

    If you get timeout in Python just submit the same solution in PyPy. My code timed out for 6 testcases in Python 3 but got accepted with max time 0.51s in PyPy3

    82|
    Permalink
    View more Comments..
  • v_balazs
    4 years ago+ 9 comments

    My solution is based on the following article from wikipedia: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

    public class Solution {
    
        static int commonChild(String a, String b){
            int[][] C = new int[a.length()+1][b.length()+1];
    
            for (int i = 0; i < a.length(); i++) {
                for (int j = 0; j < b.length(); j++) {
                    if (a.charAt(i) == b.charAt(j)) {
                        C[i+1][j+1] = C[i][j] + 1;
                    } else {
                        C[i+1][j+1] = Math.max(C[i+1][j], C[i][j+1]);
                    }
                }
            }
            for (int i = 0; i < a.length(); i++) {
            }
    
            return C[a.length()][b.length()];
        }
    
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            String s1 = in.next();
            String s2 = in.next();
            int result = commonChild(s1, s2);
            System.out.println(result);
        }
    }
    
    43|
    Permalink
    View more Comments..
  • rdn32
    7 years ago+ 11 comments

    Using Python, I was having some trouble getting test case #5 running sufficiently quickly to pass. One of my problems was to do with unnecessarily making the memory use quadratic in the problem size, but that's kind of an algorithm problem. The other is specific to Python, and is a bit subtle so I thought it would be worth describing: although the program can be written without defining a function to do the work (as it only needs to solve one case), accessing file scope variables is slower than function scope variables. Once you've got the algorithm right, this second issue makes a surprising amount of difference to performance.

    33|
    Permalink
    View more Comments..
  • nonomus
    7 years ago+ 6 comments

    Anyone who is getting the segfault error on test case #5: You are likely programming in C/C++ and are running out of stack space for your array. Use dynamic memory to fix it.

    32|
    Permalink
    View more Comments..
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature