You didn't describe how the letter prefix is chosen.
Is it assigned at random?
Is it one of their initials, etc?
Do you go A001, B001, ..., Z001, A002, B002 etc?
Does the user get to pick it?
This will affect your 'best way'.
BTW, this only gives you 26*1000=26000 possible combos. Will...