cf.completefrontend
ALGORITHMS IN FRONTEND WORK · CORE

Fuzzy matching

Check whether the letters of a short query appear in order inside a longer name, and score how good the match looks.

Time O(n)Space O(1)4 practice problemsStep-through picture

The idea

In a command palette you can type gco and see Git: Commit at the top. The letters g, c, o don't sit next to each other in the name, but they appear in the right order. A query whose letters appear in order inside a name, with gaps allowed, is a subsequence of it. That is the core test of fuzzy matching.

Many names match a short query, so each match also gets a score. Matching letters earn points. Letters right after the previous match (consecutive) earn a bonus, and letters at the start of a word (after a space, -, _, or /) earn a bigger bonus, because people tend to type the first letters of words. Results are sorted by score.

The simplest version walks the name once, left to right, with an index qi into the query. Each time the current name letter equals query[qi], it counts as a match and qi moves on. If qi reaches the end of the query, it matched. This greedy walk takes the first possible letter each time, which is fast and usually good enough.

An everyday example

Spotting your initials on a list of names

Someone tells you a street name contains the letters M, S, T in that order. You scan each street name left to right and tick off M, then look for S after it, then T after that. "Main Street" passes. "Master Plan" passes too, but it feels like a weaker guess. Main Street's letters start words, so you rank it higher.

How the example maps to the code
In the exampleIn the code
The letters you were toldquery, lowercased to q
The next letter you're looking forq[qi]
Ticking off a letterscore += 1 and qi++
A letter that starts a wordi === 0 or the previous character is a space, -, _, or /
Two ticked letters side by sideprevious === i - 1, a consecutive bonus

From the slow way to fuzzy matching

  1. Start with the obvious filter: keep the names where name.includes(query). Typing gtp to find Go to Path finds nothing, because the letters g, t, p are not next to each other. People type the first letters of words, so a plain substring search is too strict.
  2. Relax the test: the query's letters must appear in the name in the same order, with gaps allowed. That is a subsequence test, and it needs one pass with two indexes: i over the name and qi over the query. When text[i] equals q[qi], move qi on. Taking the earliest matching letter each time never hurts, because it leaves the most name for the letters still to find.
  3. Now many names match a short query, so they need a rank. Ask what makes a match feel right. Letters that start words feel right, because the user typed initials. Letters right next to each other feel right, because the user typed part of a word. Scattered letters in the middle of words feel like an accident.
  4. Turn those feelings into points during the same pass: 1 for each matched letter, 2 more when it's right after the previous match, and 3 more when it starts a word. Return -1 if some query letter was never found, then sort by score with a fixed tie-breaker. That one pass with bonuses is fuzzy matching.

How it works

  1. Lowercase both strings so G matches g: q and text.
  2. Set score = 0, qi = 0 (the next query letter to find), and previous = -2 (where the last match was; -2 means none yet).
  3. Walk i over text. Stop early if every query letter is found.
  4. If text[i] isn't q[qi], move on.
  5. If it is, add 1. Add 2 more if it is right after the previous match, and 3 more if it starts a word. Then set previous = i and qi++.
  6. After the walk, return score if qi === q.length, or -1 if some query letter was never found.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function fuzzyScore(query, candidate) {
  2. const q = query.toLowerCase();
  3. const text = candidate.toLowerCase();
  4. let score = 0;
  5. let qi = 0;
  6. let previous = -2;
  7. for (let i = 0; i < text.length && qi < q.length; i++) {
  8. if (text[i] !== q[qi]) continue;
  9. score += 1;
  10. if (previous === i - 1) score += 2;
  11. if (i === 0 || " -_/".includes(text[i - 1])) score += 3;
  12. previous = i;
  13. qi++;
  14. }
  15. return qi === q.length ? score : -1;
  16. }

How fast it is

TimeO(n)
Extra memoryO(1)

Each character of the name is looked at once, and only a few counters are stored. The lowercase copies are O(n) if you count them.

  • Best caseO(n)

    The name starts with the query, so the loop stops after q.length letters. Lowercasing both strings still reads the whole name once.

  • Average caseO(n)

    A typical name: the loop walks part or all of it, one step per character.

  • Worst caseO(n)

    The last query letter is missing or is the last letter of the name, so the loop reads all n characters. Ranking k names adds O(k log k) for the sort.

Common mistakes

  • Using includes or indexOf on the whole query. That only finds letters that are next to each other, which isn't fuzzy.
  • Forgetting to lowercase. Users don't type capitals in a command palette.
  • Sorting results without a tie-breaker. Equal scores then appear in a different order from one keystroke to the next.
  • Assuming greedy gives the best possible score. It gives a valid match; for the best one, compare every placement with dynamic programming.

When to use it

Look for these clues in a problem:

  • The user types a few letters and expects matching items even when the letters aren't next to each other.
  • The question mentions a command palette, quick open, file finder, or search-as-you-type.
  • You must check whether one string's letters appear in order inside another.
  • Results must be ranked by how well they match, with clear tie-breaking rules.

Check yourself

Answer each one in your head first, then open it.

Why does taking the earliest matching letter never miss a match?

Any placement that uses a later letter can be changed to use the earlier one instead, and that leaves at least as much of the name for the remaining letters. So if any placement exists, the greedy one finds one too.

What is the score of gtp against Go to Path?

12. Each of g, t, and p starts a word, so each earns 1 + 3 = 4. None of them touch each other, so there's no side-by-side bonus.

Why does previous start at -2 instead of -1?

At i = 0, the check is previous === i - 1, which is -1. Starting at -1 would give the very first letter a side-by-side bonus it didn't earn.

Why can the greedy score be lower than the best possible score?

Greedy takes the first matching letter, which may not be at a word start, while a later copy of that letter is. For ops in Open Project Settings, greedy scores 11 but the best placement scores 12.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

For the yes-or-no answer, the loop keeps this rule: after looking at text[0] to text[i], the first qi query letters are matched in order inside that part, and no placement could fit more query letters into it. Taking the earliest possible spot for each letter keeps the rule, because any other placement uses a later spot and leaves less room for the rest. This is called greedy staying ahead.

So if the loop ends with qi < q.length, no placement of all the letters exists, and -1 is right. If qi === q.length, the greedy placement is a real placement, so the name matches. The loop always ends because i grows by one each time and stops at text.length.

The score is a different story. It scores the greedy placement, which isn't always the best one. For ops against Open Project Settings, greedy takes the p at index 1, right after the o, and scores 11. Taking the p that starts Project instead would score 12, because a word start is worth more than touching the previous letter. Finding the best placement needs dynamic programming over every placement.

Going deeper

3 more ideas

Why greedy finds every match

If the query's letters appear in order anywhere in the name, taking the earliest possible spot for each letter never hurts: it leaves the most room for the letters after it. So the greedy walk says "matched" exactly when the query is a subsequence. The score is another story: an earlier letter can miss a word-start bonus that a later one would get. Tools that want the best score use dynamic programming over all placements.

How fast it is

One pass over each name, so scoring one name is O(n) for a name of length n. Ranking k names is O(total length) plus sorting, O(k log k). That is quick enough to rerun on every keystroke for thousands of commands.

Making the order of results predictable

Two names often get the same score. Decide the tie-breaker up front, such as the shorter name first, then alphabetical. Without one, results can jump around between keystrokes, which feels broken to users.

Work it by hand

Every step in a table, with why

Score the query gopa against Go to Path. Two word starts and two runs of side-by-side letters both earn bonuses, and the loop stops before the end of the name.

query = "gopa", candidate = "Go to Path"

Stepitext[i]q[qi]scoreWhat happensWhy
10gg4match: 1 + word start 3i === 0, so it starts a word. previous is -2, so there is no side-by-side bonus. Now qi = 1, previous = 0.
21oo7match: 1 + next to previous 2previous === i - 1, so the letters touch. The letter before is g, not a separator, so no word start.
32 p7skipA space is not p. Gaps are allowed, so just move on.
43tp7skipNot p either.
54op7skipStill looking for p.
65 p7skipAnother space. It doesn't match, but it makes the next letter a word start.
76pp11match: 1 + word start 3The letter before is a space. The previous match was at index 1, so no side-by-side bonus.
87aa14match: 1 + next to previous 2Right after the p. Now qi = 4 = q.length, so the loop condition fails before index 8.

It returns 14. The loop ended early because every query letter was found; the last two letters of path were never looked at.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Fuzzy matchingO(n)O(1)A command palette or quick finder that reruns on every keystroke over thousands of names. One pass per name is fast enough.
Substring search with includesO(n · m)O(1)Users type whole words or exact parts, like a search box over article titles. That bound is the worst case of a simple search; engines are often faster.
Best-placement dynamic programmingO(n · m)O(n · m)The ranking must be as good as possible, and names are short enough that a small table per name is cheap.
Edit distance for typosO(n · m)O(m)Users misspell, like setings for settings. Fuzzy matching can't fix a wrong or extra letter; edit distance counts them.

Extra memory: O(1) for the loop: score, qi, previous, and i. The two lowercase copies take O(n) if you count them.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Fuzzy matching and the other approaches, on a scale where each line up is 10 times more steps.
  • Fuzzy matching O(n)
  • Substring search with includes, Best-placement dynamic programming, Edit distance for typos O(n · m)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Fuzzy matching101,0001 million
Substring search with includes1001 million1 trillion
Best-placement dynamic programming1001 million1 trillion
Edit distance for typos1001 million1 trillion

Inputs that need care

5 tricky inputs
An empty query: fuzzyScore("", "Anything")
qi < q.length is false at once, so the loop never runs and it returns 0. Every name matches with the same score. Most palettes show all items in their normal order in this case.
Letters out of order: fuzzyScore("ab", "ba")
b is skipped while looking for a, the a at index 1 matches, and then the name ends with qi = 1. It returns -1.
A repeated query letter: fuzzyScore("ee", "Dev")
Each query letter needs its own letter in the name. Dev has only one e, so it returns -1. Delete has three, so fuzzyScore("ee", "Delete") returns 2.
camelCase names: fuzzyScore("gun", "getUserName")
Only a space, -, _, or / counts as a word break, and the text is lowercased first. So U and N earn no word-start bonus and the score is only 6. Check for a lowercase letter followed by a capital before lowercasing to reward camelCase.
Accents: the user types cafe for Café
toLowerCase keeps the accent, so e doesn't match é. Normalize both strings with normalize("NFD") and strip the accent marks if they should match.

Variations and follow-ups

Twists interviewers add

Best placement with dynamic programming

Fill a table where each cell is the best score for matching the first qi query letters with the last one placed at name index i. Each cell looks at the best earlier cell, plus the bonuses. It costs O(n * m) for a query of length m but always finds the highest score. Tools like fzf with its default algorithm score this way.

Returning the matched positions

Push i into a list every time a letter matches. The UI uses that list to bold the matched letters in each result, which helps people see why an item matched.

Filtering faster as the user types

Adding a letter to the query can only remove matches: if gopa matches a name, so does gop. So on each new keystroke, filter the previous matches instead of the full list. This makes long lists feel instant.

File-path bonuses

File finders add rules such as "matches in the file name beat matches in the folder path" and "a match right after / starts a word". The loop is the same; only the bonus rules change.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "command palette", "quick open", "letters in order", "subsequence", or "rank the results". If letters can be wrong, not just missing, it's edit distance instead.
  • Explain it in two layers: first the two-index subsequence test and why the earliest letter is safe, then the bonuses as a separate scoring rule. Say out loud that greedy finds every match but not always the best score.
  • Test by hand: an empty query, a query longer than the name, letters out of order, and mixed upper and lower case. Then score one name and check each bonus.
  • Expect the follow-up "two names have the same score; which comes first?". Pick a fixed rule, such as shorter name first and then alphabetical, so results don't jump between keystrokes.

Where frontend code uses it

The same idea in real UI code
  • VS Code's Quick Open and command palette, and similar finders in other editors, match file and command names this way, rewarding word starts and consecutive letters.
  • Command menus in web apps (often opened with Ctrl+K or Cmd+K) filter and rank actions on every keystroke with a fuzzy score.
  • Terminal tools like fzf use the same idea with more detailed bonuses for word boundaries and consecutive matches.

Related algorithms