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 630 Discussions, By:

recency

Please Login in order to post a comment

  • wilsonthongwk
    4 days ago+ 0 comments

    here is a solution with time complexity = O(N^2) and space complexity = O(2*N) = O(N). It passes all test cases

    see comments in the code for explanation.

    int commonChild(string s1, string s2) {
        
        /*
        denote dp[i][j] is the length of longest child between
        s1[0...i] and s2[0...j]
        
        consider sub-problems of dp[i][j].
        bool ismatch = s1[i] == s2[j];
        dp[i][j] = max(dp[i-1][j-1]+ismatch, // both s1[i],s2[j] are skipped or matched 
                   dp[i-1][j], // skip s1[i] 
                   dp[i][j-1]) // skip s2[j]
                   
        initially,
        dp[-1][-1] = 0
        dp[-1][0] = 0
        dp[0][-1] = 0
                 
        update dp by 
        dp[0][0] -> dp[0][1] -> dp[0][2] -> ... -> dp[0][N-1] ->
        dp[1][0] -> dp[1][1] -> dp[1][2] -> ... -> dp[1][N-1] ->
        ...
        dp[N-1][N-1]
        
        and the final result is dp[N-1][N-1] 
        
        the actual storage for dp[][] can be reduced to dp[0..1][0...N-1]
        when we iterate i at outter loop, and j at inner loop. 
        */
        const auto N = s1.size();
        assert(s2.size() == N);
        vector<vector<int>> dp(2, vector<int>(N+1, 0)); // N+1 is for the dp[i][-1] which is always 0
        
        auto IdxI = [](int i){
            return (i+2)%2;
        };
        auto IdxJ = [N](int j){
            return (j+(N+1))%(N+1);
        };
        
        bool ismatch = false;
        for (signed i=0; i<N; ++i) {
            for (signed j=0; j<N; ++j) {
                ismatch = s1[i]==s2[j];
                dp[IdxI(i)][IdxJ(j)] = max({
                    dp[IdxI(i-1)][IdxJ(j-1)]+ismatch,
                    dp[IdxI(i)][IdxJ(j-1)],
                    dp[IdxI(i-1)][IdxJ(j)]
                    });
            }
        }
        
        return dp[IdxI(N-1)][IdxJ(N-1)];
    }
    
    0|
    Permalink
  • tangjch15
    3 weeks ago+ 0 comments

    DP in C++ code, simple version

    int max_substr(const std::string& s1, const std::string& s2, int pos1, int pos2, std::vector<std::vector<int>>& mem) {
      if (pos1 == s1.size() || pos2 == s2.size()) {
        return 0;
      }
      if (mem[pos1][pos2] != -1) {
        return mem[pos1][pos2];
      }
      if (s1[pos1] == s2[pos2]) {
        mem[pos1][pos2] = 1 + max_substr(s1, s2, pos1 + 1, pos2 + 1, mem);
        return mem[pos1][pos2];
      }
      mem[pos1][pos2] = std::max(max_substr(s1, s2, pos1, pos2 + 1, mem), max_substr(s1, s2, pos1 + 1, pos2, mem));
      return mem[pos1][pos2];
    }
    
    int commonChild(string s1, string s2) {
      std::vector<std::vector<int>> mem(s1.size(), std::vector<int>(s2.size(), -1));
      return max_substr(s1, s2, 0, 0, mem);
    }
    
    0|
    Permalink
  • akolodziejczak11
    3 weeks ago+ 0 comments
    public static int commonChild(string s1, string s2)
        {
            int m = s1.Length + 1, n = s2.Length + 1;
            int[,] LCS = new int[m, n];
            for (int i = 1; i < m; i++)
            {
                for (int j = 1; j < n; j++)
                {
                    if (s1[i - 1] == s2[j - 1]) LCS[i, j] = LCS[(i - 1), (j - 1)] + 1;
                    else LCS[i, j] = Math.Max(LCS[(i - 1), j], LCS[i, (j - 1)]);
                }
            }
            return LCS[(m - 1), (n - 1)];
        }
    
    0|
    Permalink
  • prsephton
    1 month ago+ 1 comment

    I quite liked this Python, but it turned out too slow:

    from collections import Counter
    def commonChild(s1, s2):
        ctable = Counter()
        for i  in range(len(s1)):
            for j  in range(len(s2)):
                if s1[i] == s2[j]:
                    ctable[(i, j)] = 1 + ctable[(i-1, j-1)]
                else:
                    a, b = ctable[(i, j-1)], ctable[(i-1, j)]
                    if a or b:
                        ctable[(i, j)] = max(a, b)                
        values = list(ctable.values())
        return values[-1] if values else 0
    
    0|
    Permalink
  • prsephton
    1 month ago+ 0 comments

    A C++ version:

    int commonChild(const std::string &s1, const std::string &s2) {
        std::vector<int> vtable[2];
        size_t s1_len = s1.length() + 1;
        size_t s2_len = s2.length() + 1;
        vtable[0].resize(s2_len, 0);
        vtable[1] = vtable[0];
        for (auto i = 1; i < s1_len; ++i) {
            auto &prev = vtable[(i+1)%2];
            auto &curr = vtable[i%2];
            for (auto j = 1; j < s2_len; ++j) {
                if (s1[i-1] == s2[j-1]) {
                    curr[j] = prev[j-1] + 1;
                } else {
                    if (prev[j] > curr[j-1])
                        curr[j] = prev[j];
                    else
                        curr[j] = curr[j-1];
                }
            }
        }
        return vtable[(s1_len+1)%2][s2_len-1];
    }
    
    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