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.

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

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);
    }
}

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.

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.