Contrast in regular expressions

The use of "contrast" (mutually exclusive character sets) is a good way to reduce backtracking.

Validation: exactly three digits, located at the end of string

Example task from here: we want to validate strings that have exactly three digits at the end.

First try using anchors and the dot operator:

^.+\d{3}$

This will also validate strings with four digits at the end, such as "ABCD1234". This is because . and \d are not mutually exclusive (first hint that contrast may be useful)! The dot will match the fourth digit (fourth considered from the end).

There's two ways to fix this.

This can be "patched up" ad hoc by making sure that there is no digit before the third digit, i.e. we may do a negative lookbehind to ensure the last matched dot is not a digit (again, hint at contrast!).

^.+(?<!\d)\d{3}$

This works! This essentially enforces contrast for a single preceding character. However we can also just directly express the contrast, avoiding the negative lookbehind and ending up with a clean efficient regex.

^\D+\d{3}$

Note however that the regex with the lookbehind will also match "2ABCD123" whereas the version with contrast will not (unless you remove the start of line anchor), so they are not exactly identical. Which one is appropriate depends on how you interpret the task: "exactly three digits at the end" vs. "exactly three digits, at the end". :-)

Validation: string contains at least one lowercase letter

This could for example be useful for password validation. Example from here (condition 2). We'll do a lookahead to find a lowercase character.

If we use the start quantifier, both greedy and non-greedy, we'll have to do either backtracking or many expanding steps.

.*[a-z]

This will first expand all the way to the end of the string, then backtrack.

.*?[a-z]

This will instead start with the first character, then expand step by step.

Instead, we can use the contrast:

[^a-z]*[a-z]

Essentially we are satisfied once we reach a lowercase character. Because this is not about matching but validation, we do this in a lookahead, starting from the beginning of the string (\A; which only differs from ^ in multiline mode):

\A(?=[^a-z]*[a-z])

If we just want to consume the whole string if its validated, gobble with up with .*

\A(?=[^a-z]*[a-z]).*

We can also use an atomic group which instructs the regex engine not to backtrack if the lowercase character is not found.

(?>[^a-z]*)[a-z]

Or possessive version (which is syntactic sugar for the atomic group):

[^a-z]*+[a-z]—but we'll 

You can make a regex fail faster using possessive quantifiers or atomic groups. Also see this note on avoiding catastrophic backtracking.