Regular Expression Matching First Non-Repeated Character
<p><strong>TL;DR</strong></p>

<p><code>re.search("(.)(?!.*\1)", text).group()</code> doesn't match the first non-repeating character contained in text (it always returns a character at or before the first non-repeated character, or before the end of the string if there are no non-repeated characters. My understanding is that re.search() should return None if there were no matches).
I'm only interested in understanding why this regex is not working as intended using the Python <code>re</code> module, not in any other method of solving the problem</p>

<p><strong>Full Background</strong></p>

<p>The problem description comes from <a href="https://www.codeeval.com/open_challenges/12/">https://www.codeeval.com/open_challenges/12/</a>. I've already solved this problem using a non-regex method, but revisited it to expand my understanding of Python's <code>re</code> module.
The regular expressions i thought would work (named vs unnamed backreferences) are: </p>

<p><code>(?P&lt;letter&gt;.)(?!.*(?P=letter))</code> and <code>(.)(?!.*\1)</code> (same results in python2 and python3)</p>

<p>My entire program looks like this</p>

<pre><code>import re
import sys
with open(sys.argv[1], 'r') as test_cases:
    for test in test_cases:
        print(re.search("(?P&lt;letter&gt;.)(?!.*(?P=letter))",
                        test.strip()
                       ).group()
             )
</code></pre>

<p>and some input/output pairs are:</p>

<pre><code>rain | r
teetthing | e
cardiff | c
kangaroo | k
god | g
newtown | e
taxation | x
refurbished | f
substantially | u
</code></pre>

<p>According to what I've read at <a href="https://docs.python.org/2/library/re.html">https://docs.python.org/2/library/re.html</a>:</p>

<ul>
<li><code>(.)</code> creates a named group that matches any character and allows later backreferences to it as <code>\1</code>. </li>
<li><code>(?!...)</code> is a negative lookahead which restricts matches to cases where <code>...</code> does not match.</li>
<li><code>.*\1</code> means any number (including zero) of characters followed by whatever was matched by <code>(.)</code> earlier</li>
<li><code>re.search(pattern, string)</code> returns only the first location where the regex pattern produces a match (and would return None if no match could be found)</li>
<li><code>.group()</code> is equivalent to <code>.group(0)</code> which returns the entire match</li>
</ul>

<p>I think these pieces together should solve the stated problem, and it does work like I think it should for most inputs, but failed on <code>teething</code>. Throwing similar problems at it reveals that it seems to ignore repeated characters if they are consecutive:</p>

<pre><code>tooth | o      # fails on consecutive repeated characters
aardvark | d   # but does ok if it sees them later
aah | a        # verified last one didn't work just because it was at start
heh | e        # but it works for this one
hehe | h       # What? It thinks h matches (lookahead maybe doesn't find "heh"?)
heho | e       # but it definitely finds "heh" and stops "h" from matching here
hahah | a      # so now it won't match h but will match a
hahxyz | a     # but it realizes there are 2 h characters here...
hahxyza | h    # ... Ok time for StackOverflow
</code></pre>

<p>I know lookbehind and negative lookbehind are limited to 3-character-max fixed length strings, and cannot contain backreferences even if they evaluate to a fixed length string, but I didn't see the documentation specify any restrictions on negative lookahead.</p>



<p><a href="http://stackoverflow.com/a/39796953/3764814">Sebastian's answer</a> already explains pretty well why your current attempt doesn't work.</p>

<h3>.NET</h3>

<p>Since <s>you're</s> <a href="http://stackoverflow.com/users/1020526/revo">revo</a> is interested in a .NET flavor workaround, the solution becomes trivial:</p>

<pre class="lang-none prettyprint-override"><code>(?&lt;letter&gt;.)(?!.*?\k&lt;letter&gt;)(?&lt;!\k&lt;letter&gt;.+?)
</code></pre>

<p><a href="http://regexstorm.net/tester?p=(%3F%3Cletter%3E.)(%3F!.*%3F%5Ck%3Cletter%3E)(%3F%3C!%5Ck%3Cletter%3E.%2B%3F)&amp;i=tooth%0D%0Aaardvark%0D%0Aaah%0D%0Aheh%0D%0Ahehe%0D%0Aheho%0D%0Ahahah%0D%0Ahahxyz%0D%0Ahahxyza" rel="nofollow">Demo link</a></p>

<p>This works because .NET supports <strong>variable-length lookbehinds</strong>. You can also get that result with Python (see below).</p>

<p>So for each letter <code>(?&lt;letter&gt;.)</code> we check:</p>

<ul>
<li>if it's repeated further in the input <code>(?!.*?\k&lt;letter&gt;)</code> </li>
<li>if it was already encountered before <code>(?&lt;!\k&lt;letter&gt;.+?)</code><br>
(we have to skip the letter we're testing when going backwards, hence the <code>+</code>).</li>
</ul>

<hr>

<h3>Python</h3>

<p>The Python <a href="https://pypi.python.org/pypi/regex" rel="nofollow">regex module</a> also supports variable-length lookbehinds, so the regex above will work with a small syntactical change: you need to replace <code>\k</code> with <code>\g</code> (which is quite unfortunate as with this module <code>\g</code> is a group backreference, whereas with PCRE it's a recursion).</p>

<p>The regex is:</p>

<pre class="lang-none prettyprint-override"><code>(?&lt;letter&gt;.)(?!.*?\g&lt;letter&gt;)(?&lt;!\g&lt;letter&gt;.+?)
</code></pre>

<p>And here's an example:</p>

<pre class="lang-none prettyprint-override"><code>$ python
Python 2.7.10 (default, Jun  1 2015, 18:05:38)
[GCC 4.9.2] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
&gt;&gt;&gt; import regex
&gt;&gt;&gt; regex.search(r'(?&lt;letter&gt;.)(?!.*?\g&lt;letter&gt;)(?&lt;!\g&lt;letter&gt;.+?)', 'tooth')
&lt;regex.Match object; span=(4, 5), match='h'&gt;
</code></pre>

<hr>

<h3>PCRE</h3>

<p>Ok, now things start to get dirty: since PCRE doesn't support variable-length lookbehinds, we need to <em>somehow</em> remember whether a given letter was already encountered in the input or not.</p>

<p>Unfortunately, the regex engine doesn't provide random access memory support. The best we can get in terms of generic memory is a <em>stack</em> - but that's not sufficient for this purpose, as a stack only lets us access its topmost element.</p>

<p>If we accept to restrain ourselves to a given alphabet, we can abuse capturing groups for the purpose of storing flags. Let's see this on a limited alphabet of the three letters <code>abc</code>:</p>

<pre class="lang-none prettyprint-override"><code># Anchor the pattern
\A

# For each letter, test to see if it's duplicated in the input string
(?(?=[^a]*+a[^a]*a)(?&lt;da&gt;))
(?(?=[^b]*+b[^b]*b)(?&lt;db&gt;))
(?(?=[^c]*+c[^c]*c)(?&lt;dc&gt;))

# Skip any duplicated letter and throw it away
[a-c]*?\K

# Check if the next letter is a duplicate
(?:
  (?(da)(*FAIL)|a)
| (?(db)(*FAIL)|b)
| (?(dc)(*FAIL)|c)
)
</code></pre>

<p>Here's how that works:</p>

<ul>
<li>First, the <code>\A</code> anchor ensures we'll process the input string only once</li>
<li>Then, for each letter <code>X</code> of our alphabet, we'll set up a <em>is duplicate</em> flag <code>dX</code>:

<ul>
<li>The conditional pattern <code>(?(cond)then|else)</code> is used there:

<ul>
<li>The condition is <code>(?=[^X]*+X[^X]*X)</code> which is true if the input string contains the letter <code>X</code> twice.</li>
<li>If the condition is true, the <em>then</em> clause is <code>(?&lt;dX&gt;)</code>, which is an empty capturing group that will match the empty string.</li>
<li>If the condition is false, the <code>dX</code> group won't be matched</li>
</ul></li>
<li>Next, we lazily skip valid letters from our alphabet: <code>[a-c]*?</code></li>
<li>And we throw them out in the final match with <code>\K</code></li>
<li>Now, we're trying to match <em>one</em> letter whose <code>dX</code> flag is <em>not</em> set. For this purpose, we'll do a conditional branch: <code>(?(dX)(*FAIL)|X)</code>

<ul>
<li>If <code>dX</code> was matched (meaning that <code>X</code> is a duplicated character), we <code>(*FAIL)</code>, forcing the engine to backtrack and try a different letter.</li>
<li>If <code>dX</code> was <em>not</em> matched, we try to match <code>X</code>. At this point, if this succeeds, we know that <code>X</code> is the first non-duplicated letter.</li>
</ul></li>
</ul></li>
</ul>

<p>That last part of the pattern could also be replaced with:</p>

<pre class="lang-none prettyprint-override"><code>(?:
  a (*THEN) (?(da)(*FAIL))
| b (*THEN) (?(db)(*FAIL))
| c (*THEN) (?(dc)(*FAIL))
)
</code></pre>

<p>Which is <em>somewhat</em> more optimized. It matches the current letter <em>first</em> and only <em>then</em> checks if it's a duplicate.</p>

<p>The full pattern for the lowercase letters <code>a-z</code> looks like this:</p>

<pre class="lang-none prettyprint-override"><code># Anchor the pattern
\A

# For each letter, test to see if it's duplicated in the input string
(?(?=[^a]*+a[^a]*a)(?&lt;da&gt;))
(?(?=[^b]*+b[^b]*b)(?&lt;db&gt;))
(?(?=[^c]*+c[^c]*c)(?&lt;dc&gt;))
(?(?=[^d]*+d[^d]*d)(?&lt;dd&gt;))
(?(?=[^e]*+e[^e]*e)(?&lt;de&gt;))
(?(?=[^f]*+f[^f]*f)(?&lt;df&gt;))
(?(?=[^g]*+g[^g]*g)(?&lt;dg&gt;))
(?(?=[^h]*+h[^h]*h)(?&lt;dh&gt;))
(?(?=[^i]*+i[^i]*i)(?&lt;di&gt;))
(?(?=[^j]*+j[^j]*j)(?&lt;dj&gt;))
(?(?=[^k]*+k[^k]*k)(?&lt;dk&gt;))
(?(?=[^l]*+l[^l]*l)(?&lt;dl&gt;))
(?(?=[^m]*+m[^m]*m)(?&lt;dm&gt;))
(?(?=[^n]*+n[^n]*n)(?&lt;dn&gt;))
(?(?=[^o]*+o[^o]*o)(?&lt;do&gt;))
(?(?=[^p]*+p[^p]*p)(?&lt;dp&gt;))
(?(?=[^q]*+q[^q]*q)(?&lt;dq&gt;))
(?(?=[^r]*+r[^r]*r)(?&lt;dr&gt;))
(?(?=[^s]*+s[^s]*s)(?&lt;ds&gt;))
(?(?=[^t]*+t[^t]*t)(?&lt;dt&gt;))
(?(?=[^u]*+u[^u]*u)(?&lt;du&gt;))
(?(?=[^v]*+v[^v]*v)(?&lt;dv&gt;))
(?(?=[^w]*+w[^w]*w)(?&lt;dw&gt;))
(?(?=[^x]*+x[^x]*x)(?&lt;dx&gt;))
(?(?=[^y]*+y[^y]*y)(?&lt;dy&gt;))
(?(?=[^z]*+z[^z]*z)(?&lt;dz&gt;))

# Skip any duplicated letter and throw it away
[a-z]*?\K

# Check if the next letter is a duplicate
(?:
  a (*THEN) (?(da)(*FAIL))
| b (*THEN) (?(db)(*FAIL))
| c (*THEN) (?(dc)(*FAIL))
| d (*THEN) (?(dd)(*FAIL))
| e (*THEN) (?(de)(*FAIL))
| f (*THEN) (?(df)(*FAIL))
| g (*THEN) (?(dg)(*FAIL))
| h (*THEN) (?(dh)(*FAIL))
| i (*THEN) (?(di)(*FAIL))
| j (*THEN) (?(dj)(*FAIL))
| k (*THEN) (?(dk)(*FAIL))
| l (*THEN) (?(dl)(*FAIL))
| m (*THEN) (?(dm)(*FAIL))
| n (*THEN) (?(dn)(*FAIL))
| o (*THEN) (?(do)(*FAIL))
| p (*THEN) (?(dp)(*FAIL))
| q (*THEN) (?(dq)(*FAIL))
| r (*THEN) (?(dr)(*FAIL))
| s (*THEN) (?(ds)(*FAIL))
| t (*THEN) (?(dt)(*FAIL))
| u (*THEN) (?(du)(*FAIL))
| v (*THEN) (?(dv)(*FAIL))
| w (*THEN) (?(dw)(*FAIL))
| x (*THEN) (?(dx)(*FAIL))
| y (*THEN) (?(dy)(*FAIL))
| z (*THEN) (?(dz)(*FAIL))
)
</code></pre>

<p>And here's the <a href="https://regex101.com/r/Mhwxog/1" rel="nofollow">demo on regex101</a>, complete with unit tests.</p>

<p>You can expand on this pattern if you need a larger alphabet, but obviously this is <em>not</em> a general-purpose solution. It's primarily of educational interest and should <em>not</em> be used for any serious application.</p>

<hr>

<p>For other flavors, you may try to tweak the pattern to replace PCRE features with simpler equivalents:</p>

<ul>
<li><code>\A</code> becomes <code>^</code></li>
<li><code>X (*THEN) (?(dX)(*FAIL))</code> can be replaced with <code>(?(dX)(?!)|X)</code></li>
<li>You may throw away the <code>\K</code> and replace the last noncapturnig group <code>(?:</code>...<code>)</code> with a named group like <code>(?&lt;letter&gt;</code>...<code>)</code> and treat its content as the result.</li>
</ul>

<p>The only required but somewhat unusual construct is the conditional group <code>(?(cond)then|else)</code>.</p>

python regex regex-lookarounds