Regex (ECMAScript 2018 or .NET), 140 126 118 100 98 82 bytes
^(?!(^.*)(.+)(.*$)(?<!^\2|^\1(?=(|(<?(|(?!\8).)*(\8|\3$){1}){2})*$).*(.)+\3$)!?=*)
This is much slower than the 98 byte version, because the ^\1
is left of the lookahead and is thus evaluated after it. See below for a simple switcheroo that regains the speed. But due to this, the two TIOs below are limited to completing a smaller test case set than before, and the .NET one is too slow to check its own regex.
Try it online! (ECMAScript 2018)
Try it online! (.NET)
To drop 18 bytes (118 → 100), I shamelessly stole a really nice optimization from Neil's regex that avoids the need to put a lookahead inside the negative lookbehind (yielding an 80 byte unrestricted regex). Thank you, Neil!
That became obsolete when it dropped an incredible 16 more bytes (98 → 82) thanks to jaytea's ideas which led to a 69 byte unrestricted regex! It's much slower, but that's golf!
Note that the (|(
no-ops for making the regex well-linked have the result of making the it evaluate very slowly under .NET. They do not have this effect in ECMAScript because zero-width optional matches are treated as non-matches.
ECMAScript prohibits quantifiers on assertions, so this makes golfing the restricted-source requirements harder. However, at this point it's so well-golfed that I don't think lifting that particular restriction would open up any further golfing possibilities.
Without the extra characters needed to make it pass the restrictions (101 69 bytes):
^(?!(.*)(.+)(.*$)(?<!^\2|^\1(?=((((?!\8).)*(\8|\3$)){2})*$).*(.)+\3))
It's slow, but this simple edit (for just 2 extra bytes) regains all the lost speed and more:
^(?!(.*)(.+)(.*$)(?<!^\2|(?=\1((((?!\8).)*(\8|\3$)){2})*$)^\1.*(.)+\3))
^
(?!
(.*) # cycle through all starting points of substrings;
# \1 = part to exclude from the start
(.+) # cycle through all ending points of non-empty substrings;
# \2 = the substring
(.*$) # \3 = part to exclude from the end
(?<! # Assert that every character in the substring appears a total
# even number of times.
^\2 # Assert that our substring is not the whole string. We don't
# need a $ anchor because we were already at the end before
# entering this lookbehind.
| # Note that the following steps are evaluated right to left,
# so please read them from bottom to top.
^\1 # Do not look further left than the start of our substring.
(?=
# Assert that the number of times the character \8 appears in our
# substring is odd.
(
(
((?!\8).)*
(\8|\3$) # This is the best part. Until the very last iteration
# of the loop outside the {2} loop, this alternation
# can only match \8, and once it reaches the end of the
# substring, it can match \3$ only once. This guarantees
# that it will match \8 an odd number of times, in matched
# pairs until finding one more at the end of the substring,
# which is paired with the \3$ instead of another \8.
){2}
)*$
)
.*(.)+ # \8 = cycle through all characters in this substring
# Assert (within this context) that at least one character appears an odd
# number of times within our substring. (Outside this negative lookbehind,
# that is equivalent to asserting that no character appears an odd number
# of times in our substring.)
\3 # Skip to our substring (do not look further right than its end)
)
)
I wrote it using molecular lookahead (103 69 bytes) before converting it to variable-length lookbehind:
^(?!.*(?*(.+)(.*$))(?!^\1$|(?*(.)+.*\2$)((((?!\3).)*(\3|\2$)){2})*$))
^
(?!
.*(?*(.+)(.*$)) # cycle through all non-empty substrings;
# \1 = the current substring;
# \2 = the part to exclude from the end
(?! # Assert that no character in the substring appears a
# total even number of times.
^\1$ # Assert that our substring is not the whole string
# (i.e. it's a strict substring)
|
(?*(.)+.*\2$) # \3 = Cycle through all characters that appear in this
# substring.
# Assert (within this context) that this character appears an odd number
# of times within our substring.
(
(
((?!\3).)*
(\3|\2$)
){2}
)*$
)
)
And to aid in making my regex itself well-linked, I've been using a variation of the above regex:
(?*(.+)(.*$))(?!^\1$|(?*(.)+.*\2$)((((?!\3).)*(\3|\2$)){2})*$)\1
When used with regex -xml,rs -o
, this identifies a strict substring of the input that contains an even number of every character (if one exists). Sure, I could have written a non-regex program to do this for me, but where would be the fun in that?