How to find all characters in a string whose appearance is greater than 2

I have a question about alg开发者_开发问答orithm:

How to find all characters in a string whose appearance is greater than a specific number, say 2 for example efficiently?

Regards.

---

Counting sort will be extremely efficient for one-byte encodings, border case is two-byte encodings. For wider encodings it is not so efficient, but counting array may be replaced with hash table.

EDIT: By the way, that is too general solution, doing only counting phase and outputting results on the fly will be more than enough.

---

s= #your string
h=Hash.new(0)

s.each_char {|c| h[c]+=1 }
h.select {|char,count| count>2}

---

var word = "......";
var chars = word.GroupBy(w => w).Where(g => g.Count > 2).Select(g => new { character = g.Key, count = g.Count });

---

Couldn't resist to try this out.

1. Keep an internal array of 256 elements for each (ASCII) character.
2. Loop once over the input string.
3. Increment the count for given character using the ordinal value of the character as a direct access into the internal array.

Delphi implementation

Type
  TCharCounter = class(TObject)
  private
    FCounts: array[0..255] of byte;
  public
    constructor Create(const Value: string);
    function Count(const AChar: Char): Integer;
  end;

{ TCharCounter }

constructor TCharCounter.Create(const Value: string);
var
  I: Integer;
begin
  inherited Create;
  for I := 1 to Length(Value) do
    Inc(FCounts[Ord(Value[I])]);
end;

function TCharCounter.Count(const AChar: Char): Integer;
begin
  Result := FCounts[Ord(AChar)];
end;

---

I would sort the string, then just walk through it and keep a running tally for each letter. The last is just O(n) so it'll be as efficient as your sort.

---

the easier way is to use an array: occurrence[256], initialize them all with 0's

and for every char in string, occurrence[(int)char]++.

And then you just scan the occurrence to find the occurrence of characters satisfying your criterion.