Exact number of same characters in word-grep

Question

My task is to find lines with egrep in which first word contains exactly three same letters. I've tried to use backreferences but only found a way to build pattern which finds words builded from 3 or more same characters:

egrep -i '^[^[:alpha:]]*\<[a-z]*([a-z])[a-z]*(\1[a-z]*){2}\>'

Answer 1

The following matches any "word" at the beginning of a line consisting of only 3 of the same [:alpha:] character:

grep -i '^\([[:alpha:]]\)\1\1\b' 

Or, with grep's -E (--extended-regexp) or -P (aka --perl-regexp) options:

grep -iE '^([[:alpha:]])\1\1\b'

grep -iP '^([[:alpha:]])\1\1\b'

These work with GNU grep and (except for the -P version) with FreeBSD's grep. They may not work with other versions of grep.

---

If you want to match words of any length containing 3 or more of the same alpha character anywhere within them, it's a bit more difficult. You need to use a negative lookahead, which requires perl compatible regular expressions.

i.e. it cannot be done with grep -E (aka egrep, which has been deprecated).

For example:

$ grep -iP '^[[:alpha:]]*([[:alpha:]])((?:(?!\1)[[:alpha:]])*\1){2}[[:alpha:]]*\b' /usr/share/dict/words
Aaliyah
Aaliyah's
Aarau
Aargau
Aaronical
Abadan
Abbottstown
Abbottstown's
Aberdeen
Aberdeen's
...
zoozoo
zoozoos
zuzzes
zwitterionic
zygogeneses
zygomorphous
zymogeneses
zyzzyva
zyzzyvas
zzz

(according to wc -l, this matches 67117 out of the 344817 words in my /usr/share/dict/words file)

---

And, finally, to match only words with exactly 3 of the same [:alpha:] character anywhere within them:

$ grep -iP '^[[:alpha:]]*([[:alpha:]])((?:(?!\1)[[:alpha:]])*\1){2}[[:alpha:]]*\b' /usr/share/dict/words | 
  grep -viP '^[[:alpha:]]*([[:alpha:]])((?:(?!\1)[[:alpha:]])*\1){3}'

The first grep finds words with 3 or more of the same character, and the second excludes those with 4 or more.

I'm not sure if this can be done with a single regex or not.

(this matches 56820 words in my /usr/share/dict/words file).

Answer 2

I don't think you're going to be able to do that with grep and regular expressions, even with perl/pcre features like zero-length assertions and backreferences.

This is most probably some theoretical rabbit hole, but I'm out of my depth with such stuff.

So just do it in perl. The "algorithm" could be easily translated to awk, ruby, python, etc:

perl -CiI -anle 'my ($i,%l); ($n=++$l{$_})==3 ? $i++ : $n==4 ? $i-- : () for $F[0]=~/\pL/g; print if $i' file

This could be easily adapted. For instance, if you want to find words which have 3 letters repeated 3 times:

perl -CiI -anle 'my ($i,%l); ($n=++$l{$_})==3 ? $i++ : $n==4 ? $i-- : () for $F[0]=~/\pL/g; print if $i >= 3' /usr/share/dict/words
...
entertainment
...
totalitarianism

or 7 letters repeated 2 times:

perl -CiI -anle 'my ($i,%l); ($n=++$l{$_})==2 ? $i++ : $n==3 ? $i-- : () for $F[0]=~/\pL/g; print if $i >= 7' /usr/share/dict/words
...
electroencephalograph
...
telecommunication

You can also change \pL to just . to match any letter, $F[0]=~/../ to just /../ and no -a switch to match the whole line, omit -CiI to only consider ascii letters, etc.

Answer 3

There is no way to build such regex with only ERE (extended regex).

The closer with GNU grep (perl regex) (which match 3 or more repeated characters) is:

grep -P '(\w)(((?!\1)\w)*\1){2}' filename

So, removing words with 4 or more repeats, you will get an answer:

grep -P      '(\w)(((?!\1)\w)*\1){2}' filename | 
    grep -Pv '(\w)(((?!\1)\w)*\1){3}'

An alternative with GNU awk is:

awk '{
      a=$1;
      while (length(a)){
                        b=gensub(substr(a,0,1),"","g",a);
                        if(length(a)-length(b)==3){print $0;next};
                        a=b
                       }
     }' filename

It works by removing all repeats of the first character, if the removal was of 3 characters then print it, else, remove the next first letter until there are no more characters to replace (an improvement is to test only if the remaining length is equal or bigger than the repeat required).

Assuming that you want to count A as equivalent to a, then filter your file with:

cat /usr/share/dict/words | tr [[:upper:]] [[:lower:]] > words

The two solutions are similar but not equal. The two differ on words like independence from the dictionary file generated above.

Yes, independence contains 3 n's but 4 e's. Depending of which is found first the word may be included or not. Awk solution is stable and will include words in which any character is repeated exactly 3 times. A regex solution is more slipery and will match in some conditions and not in others.

Additionally, the regex will match only word characters which do not include ' (and the file contains several words with that character).

In all, the number of lines matched is (1527 more with awk):

 13758 awklist
 12231 greplist

And, removing the ' (184 more with awk):

 9236 awklist2
 9052 greplist2

Should tastelessness teleconferencing teletypewriter teletypewriters tempestuousness timelessness tintinnabulation tintinnabulations tirelessness transcontinental transgressors transubstantiation (just to list a few) be rejected?

All do have exactly 3 of one character and four (or more) of another.