Заметим, что $$$S_1=S_2$$$ для строк только двух видов: состоящих из повторения одного символа ($$$\alpha\alpha....\alpha$$$) и из повторения одного символа, за которым следует повторение другого символа ($$$\alpha\alpha....\alpha\beta\beta....\beta$$$).
Для $$$n \le 10^6$$$ максимальная длина необычной строки равна 56 и таких строк порядка двух миллионов, то можно было сгенерировать их все, отсортировать и выбрать $$$n$$$-ю из них.