Check if string has any consecutive repeating substring in it

Question

I want to accept only strings that do not have any substring repeated three times consecutively in them. The substring is not known in advance. For example, "a4a4a4123" contains "a4"; "abcdwwwabcd" - "w"; "abcde" - valid, no triple repeats.

I tried to implement it myself, but this only works for substrings with one letter:

public bool IsValid(string password)
{
    var validate = true;
    char lastLetter = ' ';
    var count = 1;

    for (int pos = 0; pos < password.Length; pos++)
    {
        if (password[pos] == lastLetter)
        {
            count++;

            if (count > 2)
            {
                validate = false;
                break;
            }
        }
        else
        {
            lastLetter = password[pos];
            count = 1;
        }
    }

    return validate;
}

Answer 1

Try this:

bool result = Regex.IsMatch(input, @".*(.+).*\1.*\1.*");

Basically, it checks if a pattern of one or more characters appears 3 or more times in the same string.

Full explanation:

First, it matches 0 or more characters at the beginning of the string. Then it captures a group of one or more. Then it matches 0 or more, and then the group again. Then 0 or more again, and then the capture again. Then 0 or more again.

If you require the string to be consecutive, try this:

bool result = Regex.IsMatch(input, @".*(.+)\1\1.*");

Also, some performance test results:

Non-consecutive: 312ms
Consecutive: 246ms

Tests were done with this program:

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

class Program
{
    public static void Main(string[] args)
    {
        string input = "brbrbr";
        Regex one = new Regex(@".*(.+).*\1.*\1.*");
        for (int i = 0; i < 5; i++)
        {
            bool x = one.IsMatch(input); //warm regex up
        }
        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < 100000; i++)
        {
            bool x = one.IsMatch(input);
        }
        sw.Stop();
        Console.WriteLine("Non-consecutive: {0}ms", sw.ElapsedMilliseconds);
        Regex two = new Regex(@".*(.+)\1\1.*");
        for (int i = 0; i < 5; i++)
        {
            bool x = two.IsMatch(input); //warm regex up
        }
        Stopwatch sw2 = Stopwatch.StartNew();
        for (int i = 0; i < 100000; i++)
        {
            bool x = two.IsMatch(input);
        }
        sw.Stop();
        Console.WriteLine("Consecutive: {0}ms", sw2.ElapsedMilliseconds);
        Console.ReadKey(true);
    }
}