Code using ArrayList and HashSet in Java i too slow

Question

I'm trying to solve a problem at open.kattis.com (https://open.kattis.com/problems/lexicography). You get a list of words and an index and you make a list of all the anagrams of the word and return the word at the specified index. My code works, but it's too slow and is exceeding the time limit (time limit is 1 second). I'm using HashSet to collect all the anagrams of current word (to avoid duplicates) and then convert to ArrayList for sorting.

Here's my attempt:

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;

public class lexicography {
    
    public static void main(String[] args) {
        
        ArrayList<String> resultat = new ArrayList<>(50);
        Scanner in = new Scanner(System.in);
        
        ArrayList<String> anagramLista;
        HashSet<String> tempLista;
        
        do {
             String ord = in.next();
             int num = in.nextInt();
             
             if(ord.compareTo("#") == 0 && num == 0)
                 break;
             
             tempLista = new HashSet<>(fakultet(ord.length()));
             
             hittaAnagram("", ord, tempLista);
             anagramLista = new ArrayList<>(tempLista);
             Collections.sort(anagramLista);
             
             resultat.add(anagramLista.get(num-1));
             
        }while(true);
        
        in.close();
        
        for(String s: resultat) {
            System.out.println(s);
        }
    }
    
    static int fakultet(int n) {
        
        if(n == 0)
            return 1;
        else
            return n * fakultet(n-1);
    }
    
    static void hittaAnagram(String prefix, String rest, HashSet<String> listan) {
        if(rest.length() == 0) {
            listan.add(prefix);
        } else {
            for(int i = 0; i < rest.length(); i++) {
                
                hittaAnagram(prefix + rest.charAt(i), 
                             rest.substring(0, i) + rest.substring(i + 1), 
                             listan);
            }
        }
    }
}

Would it be more efficient to rewrite it using simpler datatypes (char-arrays instead of String, String-arrays instead of Lists)? Or can the code written be tweaked to execute faster?