Longest common subsequence calculator
Find the longest run of characters two strings share in the same order, gaps allowed: ABCBDAB and BDCABA share 4, for example BCBA. You get the length and one valid subsequence you can check by eye. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- String a
- ABCBDAB
- String b
- BDCABA
- Len a
- 7
- Len b
- 6
- Length
- 4
- Subsequence
- BCBA
The longest common subsequence problem asks for the longest sequence of characters that appears in the same order inside two input strings, not necessarily contiguously. It is the dynamic-programming foundation behind line-oriented diff tools, version-control merge helpers, plagiarism detectors that ignore reordering noise, and biological sequence comparison when insertions and deletions matter more than exact substring matches. This longest common subsequence calculator accepts two strings, fills a classical length table in linear time relative to the product of the lengths, reconstructs one valid LCS by backtracking, and returns both the numeric length and the subsequence string. Empty inputs are valid and yield length zero.
What a longest common subsequence is (and is not)
A subsequence of a string is any string obtained by deleting zero or more characters without reordering the survivors. A common subsequence of two strings is a string that is a subsequence of both. A longest common subsequence, or LCS, is any common subsequence whose length is maximal among all common subsequences.
Unlike a longest common substring, an LCS need not occupy a contiguous block in either input: the classic pair ABCBDAB and BDCABA admits several LCS strings of length four, such as BCBA and BDAB, depending on which ties the reconstruction chooses. Diff algorithms and DNA alignment tools care about this non-contiguous notion because real edits insert and delete symbols rather than only sliding a fixed window.
The length of an LCS is a useful similarity score; the reconstructed characters are useful when you want an explicit alignment skeleton to show next to the score.
Where the common subsequence proves useful
Computer-science courses and online judges need a reference oracle that returns a correct length and a valid subsequence for arbitrary short strings without students pasting solutions into a full IDE. Diff-adjacent product features—change summaries, merge conflict hints, log line alignment—often want the LCS length as a cheap similarity signal before running a heavier edit-distance pass. Bioinformatics teaching demos use toy DNA alphabet strings (A, C, G, T) to show how insertions and deletions still leave a long shared backbone.
Keep strings under the length cap, pin the reconstructed subsequence in tests if you care which of several equally long answers you get, and you obtain reproducible LCS results without standing up a numerical library of your own.
What you can do with it
Algorithms homework and lecture demos
Give students two short strings and verify both the LCS length and that the returned subsequence really appears in order in each input.
LMS and contest auto-grading
Mark DP assignments with a deterministic oracle that rejects bad input and never invents a longer subsequence than the classical table allows.
Diff and sequence similarity pre-checks
Score shared ordered structure between two texts or toy DNA strings before running a heavier edit-distance or alignment pipeline.
FAQ
Is LCS the same as longest common substring?
No. A substring must be contiguous; a subsequence may skip characters. This calculator solves the subsequence problem with classical dynamic programming.
What are the length limits and empty-string rules?
Each string may be at most 500 characters. Empty strings are allowed and produce length 0 with an empty subsequence.
Why can two strings have more than one longest common subsequence?
Because ties are common. ABCBDAB and BDCABA share several subsequences of length 4, such as BCBA and BDAB. The calculator returns one of them and breaks ties the same way every time, so a fixed pair always gives the same answer.
What is the LCS length useful for?
It works as a cheap similarity score. Change summaries, merge hints and log alignment can use it before running a heavier edit-distance check, and teaching demos with DNA letters show how a long shared backbone survives insertions and deletions.
How can I check that the returned subsequence is right?
Confirm that its characters appear in the same order in both inputs, skipping others as needed, and that its length matches the reported number. BCBA passes in ABCBDAB and in BDCABA, which is exactly how graders verify answers.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your stack
curl -X POST https://api.kit.forhosting.com/dev/longest-common-subsequence \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"string_a":"ABCBDAB","string_b":"BDCABA"}'const res = await fetch("https://api.kit.forhosting.com/dev/longest-common-subsequence", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"string_a": "ABCBDAB",
"string_b": "BDCABA"
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/dev/longest-common-subsequence",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"string_a": "ABCBDAB",
"string_b": "BDCABA"
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/dev/longest-common-subsequence", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"string_a":"ABCBDAB","string_b":"BDCABA"}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"string_a":"ABCBDAB","string_b":"BDCABA"}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/dev/longest-common-subsequence", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Example request
{
"string_a": "ABCBDAB",
"string_b": "BDCABA"
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "dev.longest_common_subsequence",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
Input contract, algorithm, response shape, and limits
Complexity is O(m·n) time and O(m·n) memory in the naive table form used here—fine for the length cap, deliberately simple for teaching and deterministic goldens. POST a JSON body with two required string fields: string_a and string_b (aliases a, s1, first, text_a and b, s2, second, text_b are accepted). Both may be empty; both must be true JSON strings, not numbers or arrays. Missing fields, non-string types, and over-long inputs fail with invalid_input and are not billed. On success the body echoes string_a and string_b, reports len_a and len_b, and includes length (the LCS length) plus subsequence (one LCS string, possibly empty). Internally the solver allocates a (m+1) by (n+1) integer table, sets dp[i][j] to dp[i-1][j-1]+1 when the prefixes match on the last character, otherwise the max of the up and left cells, then walks from the bottom-right corner: a matching pair appends that character and moves diagonally; otherwise a tie prefers moving up (dropping from string_a) so the reconstructed instance is stable across runtimes.
Where an LCS API earns its keep
LMS auto-graders can call the API with fixed pairs and assert both length and that the returned subsequence is a subsequence of each input, catching off-by-one table bugs that only fail on empty or single-character edge cases.
Technical questions
How do I compute the longest common subsequence of two strings?
Send string_a and string_b as JSON strings. The API returns length (LCS length) and subsequence (one maximal common subsequence), plus echoed inputs and their lengths.
Which LCS is returned when several exist?
Any LCS of maximal length is correct. This implementation uses a fixed backtrack (prefer dropping from string_a on ties) so the same inputs always yield the same subsequence string.
What does the longest common subsequence calculator cost?
The browser tool is free. API requests use prepaid KIT balance at $0.002 per successful call; invalid input is not billed.