Skip to main content
3 of 11
put the links to the answers using the 11 byte regex in proper chronological order of when they adopted it; add a .NET regex answer link(?'-
Deadcode
  • 11.9k
  • 1
  • 66
  • 52

The purpose of this post is mainly to demonstrate the full list of golfed pure regexes that solve this challenge, and the range of compatibility of each among seven different regex engines, and rank them by length, all together in one post. Others covered the best regexes before me; I am including them for completeness. I ported the Java one to three other sets of regex engines, including Python 3's regex library.

Regex (Perl / PCRE / Boost / Pythonregex), 11 bytes

^(a(?1)?b)$

Try it online! - Perl
Try it online! - PCRE1
Try it online! - PCRE2
Try it online! - Boost
Try it online! - Python import regex

Included for completeness. Already used in:

Regex (Ruby), 12 bytes

^(a\g<1>?b)$

Try it online!

Included for completeness. Already used in G B's Ruby answer.

Regex (Perl / PCRE / Java), 21 bytes

^(a(?=a*(\2?+b)))+\2$

Try it online! - Perl
Try it online! - PCRE1
Try it online! - PCRE2
Try it online! - Java

Turned out to be used in Kevin Cruijssen's Java answer, but gave it a -6 byte golf.

Regex (.NET), 22 bytes

^(a)+(?<-1>b)+$(?(1)^)

Try it online!

Included for completeness. Already used in:

Regex (Perl / PCRE / Java / .NET), 24 bytes

^(a(?=a*((?>\2?)b)))+\2$

Try it online! - Perl
Try it online! - PCRE1
Try it online! - PCRE2
Try it online! - Java
Try it online! - .NET

This is a port of the 21 byte Perl/PCRE/Java regex, with \3?+ changed to (?>\3?) to allow the regex to also work on .NET (which lacks possessive quantifiers).

Regex (Perl / PCRE / Java / Ruby / Pythonregex), 29 bytes

^(a(?=a*(?=(\3?+b))(\2)))+\2$

Try it online! - Perl
Try it online! - PCRE1
Try it online! - PCRE2
Try it online! - Java
Try it online! - Ruby
Try it online! - Python import regex

This is a port of the 21 byte Perl/PCRE/Java regex (see below) adding compatibility with engines that lack nested backreferences, but still have forward-declared backreferences and possessive quantifiers. This allows it to work in Python when using the regex library instead of re.

^           # Assert we're at the beginning of the string.
(
    a       # Match one 'a' per iteration of this loop.
    (?=
        a*  # Skip over as many 'a' as necessary to get to the first 'b'.
        (?=
            # Capture \2. If this is the first iteration, \3 will be unset, so
            # capture a single 'b' in \2. Otherwise, \2 = \3 concatenated with
            # one more 'b'.
            (
                \3?+
                b
            )
        )
        # \3 = make a copy of \2, which was captured above
        (
            \2
        )
    )
)+
\2          # Match however many 'b' we captured in \2.
$           # Assert we're at the end of the string.

Regex (Perl / PCRE / Java / Ruby / Pythonregex / .NET), 32 bytes

^(a(?=a*(?=((?>\3?)b))(\2)))+\2$

Try it online! - Perl
Try it online! - PCRE1
Try it online! - PCRE2
Try it online! - Java
Try it online! - Ruby
Try it online! - Python import regex
Try it online! - .NET

This is a port of the above, with \3?+ changed to (?>\3?) to allow the regex to work on .NET (which lacks possessive quantifiers), so it can support 6 different regex engines at once.

It is not supported by Boost, which lacks both forward-declared and nested backreferences. It might not be possible for a single regex to work on all 7 engines.

Deadcode
  • 11.9k
  • 1
  • 66
  • 52