I think I understand your problem, something like the function below would work, I think you'd have a hard time doing this in less than O(n) time.
def normalize_groups(in_list):
groups = {}
output = []
for value in in_list:
if value not in groups:
groups[value] = len(groups)
output.append(groups[value])
return output
which would return for both lists:
In [52]: normalize_groups(l1)
Out[52]: [0, 0, 0, 1, 1, 2, 2, 1, 1]
In [53]: normalize_groups(l2)
Out[53]: [0, 0, 0, 1, 1, 2, 2, 1, 1]
EDIT: nevermind, just remove the string part completely.