Can one use .NET RegEx backreference in a character class to exclude previously matched characters?

Question

The task I was trying to accomplish was that given an input pattern, e.g. 1 2 3 3 2 4 2 1, to go through a dictionary and find words that fit the given pattern. In my code, I tried taking the given string and converting it to a regular expression like so: (?<1>.)(?<2>.)(?<3>.)(\k<3>)(\k<2>)(?<4>.)(\k<2>)(\k<1>) (Before anyone starts bashing use of the dot here, since my input is a dictionary file with only real words, I left the dots to have a cleaner looking expression rather than specifying ranges of characters.) This expression manages to find the word correctly, but there's a flaw in it. The problem becomes very apparent with a pattern such as 1 2 3 4 5 6. My algorithm generates the following regular expression: (?<1>.)(?<2>.)(?<3>.)(?<4>.)(?<5>.)(?<6>.) This is wrong because it will match any 6 character string without taking into account that each group should NOT match any characters that have already been matched by previous groups. In other words, it doesn't take into account…

Accepted Answer

The answer is: no. You cannot use backreferences in character classes of .NET regular expressions. Sorry. See below for a workaround for your situation.

"it shows that \p{name} is valid syntax in a character class"

yes, it is. But the .NET documentation does not say that name will be interpreted from a backreference. It must be a unicode literal class string.

"In other words, it doesn't take into account that each letter is distinct; no repeats."

I understand that this means to match all of `e f a x` and only `f` and `x` in `e f e x`. In other words: match unique characters, do not match characters that are repeated.

Solution

I understand your question as follows: match all unique words (subexpressions, characters) in a string that have no repetition before or after itself. The basic regular expression you should use is this:

```
(subexpr)(?!.*\1)(?<!\1.+)
```

which will find the word `subexpr` only when it appears once in the matching string. for instance, if we change it to match the `e` in `e f a x` and not in `e f e x`, it will look like this:

```
(e)(?!.*\1)(?<!\1.+)
```

You can generalize this to match every unique letter in the string:

```
(.)(?!.*\1)(?<!\1.+)
```

if will match `e`, `f`, `a` and `x` in `e f a x` and only `f` and `x` in `e f e x`. This could be the generalized replacement for your expression above and you don't need to repeat the 1,2,3 etc captures anymore.

How it works

(update) Perhaps nice to know how the above regex works:

```
(subexpr)   # grab subexpression (can be any valid grouped regex)
(?!.*\1)    # negative look forward with a backrefence: if followed somewhere by itself, fail
(?<!\1.+)   # negative look backward with backref: if preceded somewhere by itself, fail
```

Applied solution

A word has a pattern. SUCCUBUS is 1 2 3 3 2 4 2 1. PAST is 1 2 3 4. Based on that pattern, a regex should match words with the same pattern: same length of the word, repetition of the same letters in the same place: PAST and RANT have the same pattern. LOOK and HEEL have the same pattern, but not HERE.

Taking the previous solution, we adjust that generally to your problem domain by sticking to the following rules:

- A unique letter is represented by `(.)(?!.*\X)(?<!\X.+)`

- A repeated letter is represented by `(.)`

- The location where repetition occurs is represented by `\X` (no parentheses!)

- `\X` means a backreference with the number of your pattern

Examples:

```
# SUCCUBUS is 1 2 3 3 2 4 2 1 (only 4 is unique)
(.)                      # nr 1 in pattern
(.)                      # nr 2 in pattern
(.)                      # nr 3 in pattern
\3                       # repeat 3
\2                       # repeat 2
(.)(?!.*\4)(?<!\4.+)     # nr 4 UNIQUE!
\2                       # repeat 2
\1                       # repeat 1

# PAST (all unique: 1 2 3 4)
(.)(?!.*\1)(?<!\1.+)    # nr 1 in pattern
(.)(?!.*\2)(?<!\2.+)    # nr 2 in pattern
(.)(?!.*\3)(?<!\3.+)    # nr 3 in pattern
(.)(?!.*\4)(?<!\4.+)    # nr 4 in pattern
```

This pattern should be easily automated into your current system.

An excellent way to test this and other regexes (just copy and paste mine) is at Regex Hero, free online SilverLight .NET regex tester. For other online testers, see my overview chart of them.

update: removed earlier irrelevant update note

Update 1: In a comment in the other solution, you say that you want to be able to match a substring that fits the pattern. Naturally, this poses a challenge with the negative look-forward/behind: as they are now, they look through the whole string. Replace the `.*` and `.+` with the relative length the expression would be at the place, pos 3 for PAST becomes then `(.)(?!.{1}\3)(?<!\3.{2})` and pos 4 would become `(.)(?!.{2}\3)(?<!\3.{3})`

Update 2: in the same way, it is possible to optimize slightly by removing the look-back in the first expression and removing the look-forward in the last, if they need to be unique: pos 1 becomes `(.)(?!.{3}\3)` and pos 4 becomes `(.)(?<!\3.{3})`

Can one use .NET RegEx backreference in a character class to exclude previously matched characters?

Solution

Problem