CODEWITHSUNDEEP
c#algorithmstring
Ian G
Ian G

Reputation: 30234

Testing for repeated characters in a string

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.

Upvotes: 8

Views: 26633

Answers (11)

BlackPauler
BlackPauler

Reputation: 11

I started looking for some info on the net and I got to the following solution. 

string input = "aaaaabbcbbbcccddefgg";
        char[] chars = input.ToCharArray();
        Dictionary<char, int> dictionary = new Dictionary<char,int>();

        foreach (char c in chars)
        {
            if (!dictionary.ContainsKey(c))
            {
                dictionary[c] = 1; //
            }
            else
            {
                dictionary[c]++;
            }
        }

        foreach (KeyValuePair<char, int> combo in dictionary)
        {
            if (combo.Value > 1) //If the vale of the key is greater than 1 it means the letter is repeated
            {
                Console.WriteLine("Letter " + combo.Key + " " + "is repeated " + combo.Value.ToString() + " times");
            }

        }

I hope it helps, I had a job interview in which the interviewer asked me to solve this and I understand it is a common question.

Upvotes: 1

Steve Jessop
Steve Jessop

Reputation: 279215

/(.).*\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...

Upvotes: 2

mqp
mqp

Reputation: 71937

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?!

:-)

Upvotes: 18

Paul U
Paul U

Reputation: 681

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))

Upvotes: 0

Jon Skeet
Jon Skeet

Reputation: 1499800

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.

Upvotes: 9

BenAlabaster
BenAlabaster

Reputation: 39806

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.

Upvotes: 9

dirkgently
dirkgently

Reputation: 111120

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.

Upvotes: 3

Davy Landman
Davy Landman

Reputation: 15439

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);   
}

Upvotes: 0

Winston Smith
Winston Smith

Reputation: 21884

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.

Upvotes: 7

xrost
xrost

Reputation: 179

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
    }

Upvotes: 6

CasperT
CasperT

Reputation: 3475

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));
}

Upvotes: 3

Related Questions