Neste laboratório, você irá construir um gerador de permutações que receberá uma string e retornará todas as permutações possíveis dos caracteres na string. Por exemplo, as possíveis permutações da string cat são cat, cta, act, atc, tac e tca. A forma recursiva de criar permutações de uma string funciona armazenando a parte fixa inicial da string (prefix), e criando permutações do restante. Por exemplo, vamos considerar a palavra machine. A primeira rodada de criação de permutações seria feita fixando o m como prefixo da string e depois criando permutações do restante da string, achine. Para o restante da string, as permutações continuam da mesma forma. Uma letra é adicionada ao prefixo, talvez o c, então o prefixo se torna mc. Então, cada uma das permutações de ahine é concatenada ao prefixo. Isso continua até que o prefixo tenha todas as letras e o restante da string esteja vazio, isso significa que uma permutação foi criada. Objetivo: Cumprir as user stories abaixo e fazer todos os testes passarem para completar o laboratório. Histórias de Usuário: 1. Você deve criar uma função chamada permuteString. 2. A permuteString função deve receber um parâmetro, uma string, e depois dois parâmetros com um valor padrão: um valor de prefixo e um array vazio para armazenar e retornar os resultados. O valor do prefixo deve ser uma string usada para acumular caracteres para formar uma permutação. A função será chamada com um único argumento, como permuteString("cat"). 3. Dentro da função, você deve verificar se o comprimento da string passada é 0. Se for, adicione o prefixo atual aos resultados e retorne os resultados. 4. Itere sobre cada caractere na string de entrada e, a cada iteração, remova o caractere atual da string e chame a função permuteString recursivamente com argumentos atualizados para construir as permutações restantes. 5. Você deve retornar o array de resultados finais. 6. Você deve garantir que as permutações sejam únicas removendo os duplicados.

Testes:

• Você deve ter uma função `permuteString`.
• Você deve usar recursão na sua função `permuteString`.
• `permuteString("far")` deve retornar `[ "far", "fra", "afr", "arf", "rfa", "raf" ]`.
• `permuteString("fcc")` deve retornar `[ "fcc", "cfc", "ccf" ]`.
• `permuteString("p")` deve retornar `[ "p" ]`.
• `permuteString("")` deve retornar `[""]`.
• `permuteString("walk")` deve retornar `["walk", "wakl", "wlak", "wlka", "wkla", "wkal", "awlk", "awkl", "alwk", "alkw", "aklw", "akwl", "lawk", "lakw", "lwak", "lwka", "lkaw", "lkwa", "kawl", "kalw", "kwal", "kwla", "klaw", "klwa"]`.
• `.
• `permuteString` deve retornar os resultados corretos.