Testing for repeated characters in a string

Question

I'm doing some work with strings, and I have a scenario where I need to determine if a string (usually a small one < 10 characters) contains repeated characters.

`ABCDE`  // does not contain repeats 
`AABCD`  // does contain repeats, ie A is repeated

I can loop through the string.ToCharArray() and test each character against every other character in the char[], but I feel like I am missing something obvious.... maybe I just need coffee. Can anyone help?

EDIT:

The string will be sorted, so order is not important so ABCDA => AABCD

The frequency of repeats is also important, so I need to know if the repeat is pair or triplet etc.

Answer 1

If the string is short, then just looping and testing may well be the simplest and most efficient way. I mean you could create a hash set (in whatever platform you're using) and iterate through the characters, failing if the character is already in the set and adding it to the set otherwise - but that's only likely to provide any benefit when the strings are longer.

EDIT: Now that we know it's sorted, mquander's answer is the best one IMO. Here's an implementation:

public static bool IsSortedNoRepeats(string text)
{
    if (text.Length == 0)
    {
        return true;
    }
    char current = text[0];
    for (int i=1; i < text.Length; i++)
    {
        char next = text[i];
        if (next <= current)
        {
            return false;
        }
        current = next;
    }
    return true;
}

A shorter alternative if you don't mind repeating the indexer use:

public static bool IsSortedNoRepeats(string text)
{
    for (int i=1; i < text.Length; i++)
    {
        if (text[i] <= text[i-1])
        {
            return false;
        }
    }
    return true;
}

EDIT: Okay, with the "frequency" side, I'll turn the problem round a bit. I'm still going to assume that the string is sorted, so what we want to know is the length of the longest run. When there are no repeats, the longest run length will be 0 (for an empty string) or 1 (for a non-empty string). Otherwise, it'll be 2 or more.

First a string-specific version:

public static int LongestRun(string text)
{
    if (text.Length == 0)
    {
        return 0;
    }
    char current = text[0];
    int currentRun = 1;
    int bestRun = 0;

    for (int i=1; i < text.Length; i++)
    {
        if (current != text[i])
        {
            bestRun = Math.Max(currentRun, bestRun);
            currentRun = 0;
            current = text[i];
        }
        currentRun++;
    }
    // It's possible that the final run is the best one
    return Math.Max(currentRun, bestRun);
}

Now we can also do this as a general extension method on IEnumerable<T>:

public static int LongestRun(this IEnumerable<T> source)
{
    bool first = true;
    T current = default(T);
    int currentRun = 0;
    int bestRun = 0;

    foreach (T element in source)
    {
        if (first || !EqualityComparer<T>.Default(element, current))
        {
            first = false;
            bestRun = Math.Max(currentRun, bestRun);
            currentRun = 0;
            current = element;
        }
    }
    // It's possible that the final run is the best one
    return Math.Max(currentRun, bestRun);
}

Then you can call "AABCD".LongestRun() for example.

Answer 2

Update Now, you'd need an array of counters to maintain a count.

Keep a bit array, with one bit representing a unique character. Turn the bit on when you encounter a character, and run over the string once. A mapping of the bit array index and the character set is upto you to decide. Break if you see that a particular bit is on already.

Answer 3

If the string is sorted, you could just remember each character in turn and check to make sure the next character is never identical to the last character.

Other than that, for strings under ten characters, just testing each character against all the rest is probably as fast or faster than most other things. A bit vector, as suggested by another commenter, may be faster (helps if you have a small set of legal characters.)

Bonus: here's a slick LINQ solution to implement Jon's functionality:

int longestRun =
    s.Select((c, i) => s.Substring(i).TakeWhile(x => x == c).Count()).Max();

So, OK, it's not very fast! You got a problem with that?!

:-)

Answer 4

I think the easiest way to achieve that is to use this simple regex

bool foundMatch = false;
foundMatch = Regex.IsMatch(yourString, @"(\w)\1");

If you need more information about the match (start, length etc)

     Match match = null;
 string testString = "ABCDE AABCD";
 match = Regex.Match(testString, @"(\w)\1+?");
 if (match.Success)
 {
  string matchText = match.Value; // AA
  int matchIndnex = match.Index;  // 6
  int matchLength = match.Length; // 2
 }

Answer 5

/(.).*\1/

(or whatever the equivalent is in your regex library's syntax)

Not the most efficient, since it will probably backtrack to every character in the string and then scan forward again. And I don't usually advocate regular expressions. But if you want brevity...

Answer 6

Since you're using 3.5, you could do this in one LINQ query:

var results = stringInput
  .ToCharArray() // not actually needed, I've left it here to show what's actually happening
  .GroupBy(c=>c)
  .Where(g=>g.Count()>1)
  .Select(g=>new {Letter=g.First(),Count=g.Count()})
;

For each character that appears more than once in the input, this will give you the character and the count of occurances.

Answer 7

This will tell you very quickly if a string contains duplicates:

bool containsDups = "ABCDEA".Length != s.Distinct().Count();

It just checks the number of distinct characters against the original length. If they're different, you've got duplicates...

Edit: I guess this doesn't take care of the frequency of dups you noted in your edit though... but some other suggestions here already take care of that, so I won't post the code as I note a number of them already give you a reasonably elegant solution. I particularly like Joe's implementation using LINQ extensions.

Answer 8

How about something like:

string strString = "AA BRA KA DABRA";

var grp = from c in strString.ToCharArray() 
        group c by c into m
        select new { Key = m.Key, Count = m.Count() };

foreach (var item in grp)
{
    Console.WriteLine(
        string.Format("Character:{0} Appears {1} times", 
        item.Key.ToString(), item.Count));
}

Answer 9

When there is no order to work on you could use a dictionary to keep the counts:

String input = "AABCD";
var result = new Dictionary<Char, int>(26);
var chars = input.ToCharArray();
foreach (var c in chars)
{
    if (!result.ContainsKey(c))
    {
        result[c] = 0; // initialize the counter in the result
    }
    result[c]++;
}

foreach (var charCombo in result)
{
    Console.WriteLine("{0}: {1}",charCombo.Key, charCombo.Value);   
}

Answer 10

The hash solution Jon was describing is probably the best. You could use a HybridDictionary since that works well with small and large data sets. Where the letter is the key and the value is the frequency. (Update the frequency every time the add fails or the HybridDictionary returns true for .Contains(key))