SDE - 1

You have been given two Strings “STR1” and “STR2” of characters. Your task is to find the length of the longest common subsequence.

A String ‘a’ is a subsequence of a String ‘b’ if ‘a’ can be obtained from ‘b’ by deletion of several (possibly, zero or all) characters. A common subsequence of two Strings is a subsequence that is common to both Strings.

You are given a cartesian plane, having ‘N’ points in the form of the array ‘PointX’ and ‘PointY’ where ‘PointX[i]’ and ‘PointY[i]’ represent the ‘X’ coordinates and ‘Y’ coordinates of the i’th point, respectively. You have to find the number of pairs satisfying the following conditions:

1. The points in the pair are distinct.
2. Euclidean distance and the Manhattan distance between the points of the pair should be equal.

Note :

1. Pair (‘P’, ‘Q’) is the same as pair (‘Q’, ‘P’).
2. Euclidean distance is given by: (( ‘X2’ - ‘X1’) ^ 2 + (‘Y2’ - ‘Y1’) ^ 2) ^ 0.5.
3. Manhattan distance is given by: |’X2’ - ‘X1’| + |’Y2’ - ‘Y1’|, where points are (‘X1’, ‘Y1’) and (‘X2’, ‘Y2’).

For example :

Let points be: (1, 2), (2, 3), (1, 3)
The Euclidean distance between points (1, 2) and (1, 3) is: 1
The Manhattan distance between points (1, 2) and (1, 3) is: 1
The Euclidean distance between points (2, 3) and (1, 3) is: 1
The Manhattan distance between points (2, 3) and (1, 3) is: 1
So the pairs can be: [(1, 2), (1, 3)] and [(2, 3), (1, 3)].
So the number of pairs is 2.