Sir,

I think the BruteForce solution can be slightly modified to look like this

public static int lcsRecursive(String s1, String s2, int i1, int i2, int count) {

if (i1 == s1.length() || i2 == s2.length()) {

// we reached the end

return count;

}

if (s1.charAt(i1) == s2.charAt(i2)) {

//so increment the count and try to recursively match for remaining lenght (the next set of chars)

return lcsRecursive(s1,s2,i1+1,i2+1,count+1);

}

```
//if strings do not match create two new recursive calls by skipping one char separately
int c1 = lcsRecursive(s1,s2,i1+1, i2, 0);
int c2 = lcsRecursive(s1,s2,i1, i2+1, 0);
return Math.max(count, Math.max(c1,c2));
}
```

And then the complexity would be O(2^(m+n)) and not 3^(m+n)

The above code can be expressed by recurrence relation

T(n) = 1 + T(n-1) + T(n-1)

And so

T(n) = O(2^(m+n))

please let me know …