Das ist doch ganz einfach. Durch entsprechenden Einsatz von mehr Speicher kannst du die Laufzeit extrem drücken. Du legst dir ein Array an für die Buchstaben von a-z und initialisierst es mit 0. Dann gehst du den ersten String durch und erhöst bei jedem Buchstaben die entsprechende Stelle im Array. Das gleiche machst du mit einem zweiten Array und dem anderen String. Nun musst du nur das erste Array duchgehen und gucken ob dort immer kleinergleiche Zahlen als im anderen Array drinstehen. So musst du jeden String nur einmal durchgehen.

Um noch performanter zu werden. Legst du nur das erste Array an, um beim durchgehen des zweiten Strings ziehst du bei der entsprechenden Arrayposition wieder einen ab. Wenn irgendwann etwas kleiner 0 dabei entsteht geht es nicht.