Creating unique keys from list [duplicate]

Question

I have the following (example) list:

list = {"b", "a", "b", "b", "a", "c", "c", "c", "d", "b", "aa"};

and want to distinguish its elements by appending a counter in the following manner:

ord = Ordering @ Ordering @ list;

Part[#, ord]& @ Flatten[#, 1]& @ 
   MapIndexed[{#1, Last @ #2}&, #, {2}] & @ Gather @ Sort @ list

{{"b", 1}, {"a", 1}, {"b", 2}, {"b", 3}, {"a", 2}, {"c", 1}, {"c", 2}, {"c", 3}, {"d", 1}, {"b", 4}, {"aa", 1}}

This solution is somehow "expensive" (three ordering / sorting) operations, so the question is:

Are there more efficient alternatives?

Answer 1

list = {"b", "a", "b", "b", "a", "c", "c", "c", "d", "b", "aa"}
c = Association[# -> 0 & /@ Union@list]
{#, c[#] += 1} & /@ list

{{"b", 1}, {"a", 1}, {"b", 2}, {"b", 3}, {"a", 2}, {"c", 1}, {"c", 2}, {"c", 3}, {"d", 1}, {"b", 4}, {"aa", 1}}

Answer 2

Clear[f]
f[_] = 0;
(f[#] = f[#] + 1; {f[#], #}) & /@ list

{{1, "b"}, {1, "a"}, {2, "b"}, {3, "b"}, {2, "a"}, {1, "c"}, {2,
"c"}, {3, "c"}, {1, "d"}, {4, "b"}, {1, "aa"}}

Answer 3

Functional style:

FoldPairList[With[{c = Lookup[#1, #2, 1]}, 
   {{#2, c}, Append[#1, #2 -> c + 1]}] &, <||>, list]