Please subscribe to the official Codeforces channel in Telegram via the link: ×

jayantjpr's blog

By jayantjpr, 5 years ago, In English,

Hi friends,

I was solving a question on SPOJ ( to calculate the Edit Distance between two strings (

My Claim is:

Given two strings A & B
 Edit Distance(A,B) = max(|A|,|B|) - |Longest common sub-sequence(A,B)|.
(where |A| means length of string A)

Is there something wrong with the above claim? If yes, could you help me find out a test case on which it fails?

I tried submitting the code (using the above claim), but got a wrong answer. I am already aware of the conventional DP solution as shown on the wikipedia page.

Thanks for you help!



Read more »