# LCS

> Find the longest common subsequence of two strings.

URL: https://docs.hotkv.com/commands/lcs/

```
LCS key1 key2 [LEN] [IDX] [MINMATCHLEN min-match-len] [WITHMATCHLEN]
```

- Group: String
- Complexity: O(N*M) where N and M are the lengths of the two strings
- HotKV Cloud: all plans
- On-Premise: no license needed

`LCS` compares the strings at `key1` and `key2` and finds their longest common
subsequence: the longest run of characters that appears in both, in the same
order, but not necessarily next to each other. It is useful for diffing short
texts or measuring how similar two values are. A missing key counts as an
empty string.

## Options

| Option | Effect |
| --- | --- |
| `LEN` | Return only the length of the subsequence. |
| `IDX` | Return the positions of the matching ranges in both strings, and the length. |
| `MINMATCHLEN min-match-len` | With `IDX`, leave out ranges shorter than this. |
| `WITHMATCHLEN` | With `IDX`, add the length of each range to its entry. |

`LEN` and `IDX` cannot be combined. With `IDX`, ranges are listed from the end
of the strings towards the start, and each position pair is the first and
last offset of the range, both included.

## Return value

| Case | RESP2 | RESP3 |
| --- | --- | --- |
| No option | Bulk string: the subsequence | Bulk string |
| `LEN` | Integer: its length | Integer |
| `IDX` | Array `["matches", [...], "len", length]` | Map with the keys `matches` and `len` |

Each entry in `matches` is an array of two ranges, `[start1, end1]` in the
first string and `[start2, end2]` in the second, followed by the range length
when `WITHMATCHLEN` is given.

Errors:

- `ERR The specified keys must contain string values` when either key holds
  another type.
- `ERR If you want both the length and indexes, please just use IDX.` when
  `LEN` and `IDX` are both given.
- `ERR Insufficient memory, transient memory for LCS exceeds proto-max-bulk-len`
  when the strings are too long to compare.
- `ERR syntax error` for an unknown option.

## Examples

```
127.0.0.1:6379> MSET a "redwood" b "deadwood"
OK
127.0.0.1:6379> LCS a b
"edwood"
127.0.0.1:6379> LCS a b LEN
(integer) 6
127.0.0.1:6379> LCS a b IDX MINMATCHLEN 2 WITHMATCHLEN
1) "matches"
2) 1) 1) 1) (integer) 2
         2) (integer) 6
      2) 1) (integer) 3
         2) (integer) 7
      3) (integer) 5
3) "len"
4) (integer) 6
```

## Compatibility

Same as Redis 7 and Valkey 8.

## See also

[GETRANGE](https://docs.hotkv.com/commands/getrange/index.md), [STRLEN](https://docs.hotkv.com/commands/strlen/index.md),
[GET](https://docs.hotkv.com/commands/get/index.md)