Descriptive naming
Set<String> perm(String input)
I would call this
Set<String> permute(String input)
When I see perm, my first thought is someone making straight hair curly. My second thought is that it might be short for permanent. Well after that I realize that in this context, you are permuting things. In my opinion, the extra three letters increases readability greatly.
Set<String> perm = new HashSet<String>();
Ignoring the confusion with naming a variable the same as the method using it, I'd go with
Set<String> permutations = new HashSet<>();
Now I know what's supposed to be in there.
Unless you are compiling against an old Java version, you don't need to write out String the second time. The compiler will figure it out.
Avoid casts
char[] arr = input.toCharArray();
While this often helps when processing something character by character, I don't think it does so here.
perm.add(String.valueOf(arr[0]));
This could be
permutations.add(input.substr(0, 1));
So rather than converting from a String to a character array, then getting one character, then converting that character to a String, we just take a single character substr which returns the String that we want. Since a String is immutable, this can use the original backing array to hold the data. The other version would likely allocate new memory because it's not obvious that it's just taking a substring.
But even better might be
permutations.add("");
Then we can simplify the gating test to just check for null. And we can put the rest of the logic in the loop.
for (char current : input.toCharArray())
{
permutations = permute(current, permutations);
}
Yes, I did change the name of findPerm, and I changed it to take a character rather than a String. I didn't like the name findPerm because you aren't finding anything. You are generating permutations.
If we change the first parameter to be a character rather than a String, we can use it as a character later.
The other version may be slightly more efficient, but at the cost of additional coding complexity.
And now we are processing the String character by character, so we convert it to a character array. We don't need i, as we can work with the characters directly.
Don't do unnecessary work
You have
Set<String> perms = new HashSet<String>(perm);
and
perms.remove(each);
But if you change the first to
Set<String> permutations = new HashSet<String>();
Then you don't need the second line. There is no reason to put the partial permutations in the results.
Don't Repeat Yourself (DRY)
perms.addAll(addAtEachIndex(each, next));
So addAtEachIndex creates a Set just to return it and add to another Set. Why bother?
addAtEachIndex(each, next, permutations);
If we pass the Set into the method, we can add to it directly. So we check for duplicates once, not twice.
Choose your datatype
finalPerms.add(each.substring(0,i+1) + next +each.substring(i+1, each.length()));
You are doing a lot of String manipulation in this section and it's not really necessary. Consider what happens if you leave next as a character rather than a String.
StringBuilder permutation = new StringBuilder(each);
permutation.append(next);
permutations.add(permutation.toString());
for (int i = each.length(); i > 0; i--)
{
permutation.setCharAt(i, permutation.charAt(i - 1));
permutation.setCharAt(i - 1, next);
permutations.add(permutation.toString());
}
This also works with a StringBuilder rather than a String.
Now, rather than copying two substrings and a single character String into a new String, we only copy once. We do three character operations rather than five String operations. And we can keep reusing the same StringBuilder as a base.
Summary
public static Set<String> permute(String input)
{
Set<String> permutations = new HashSet<String>();
if (input == null)
{
permutations.add(input);
return permutations;
}
permutations.add("");
for (char current : input.toCharArray())
{
permutations = _permute(current, permutations);
}
return permutations;
}
private static Set<String> _permute(char next, Set<String> partials)
{
Set<String> permutations = new HashSet<String>();
for (String partial : partials)
{
addAtEachIndex(partial, next, permutations);
}
return permutations;
}
private static void addAtEachIndex(String partial, char next, Set<String> permutations)
{
StringBuilder permutation = new StringBuilder(partial);
permutation.append(next);
permutations.add(permutation.toString());
for (int i = partial.length(); i > 0; i--)
{
permutation.setCharAt(i, permutation.charAt(i - 1));
permutation.setCharAt(i - 1, next);
permutations.add(permutation.toString());
}
}
I also made all the methods static as they weren't using any object state.
Time complexity
If we call the outer permute once, we call the inner _permute about \$n\$ times, where \$n\$ is the length of the input.
The first time we call the inner _permute, it calls addAtEachIndex once. The second time, once. The third time, twice. So on the \$i\$th time, we call it \$(i-1)!\$ times if there are no duplicate characters in the String. If there are duplicate characters, we call it fewer times.
The first time that we call the inner _permute, each call to addAtEachIndex iterates 0 times. The second time, one time. The third time, twice. The fourth time, six iterations. Yep, \$(i - 1)!\$ again.
Perhaps the simplest way to think about this are that there are \$n+1\$ steps to find the permutations. On the \$i\$th step, we generate \$(i-1)!\$ permutations. So for a given input length of \$n\$, we generate \$ \sum_{i=0}^{n} i! \$ permutations. But that's just \$\mathcal{O}(n!)\$ because it is smaller than \$ (n+1)!\$ which is \$\mathcal{O}(n!)\$.
This is as efficient as we can get asymptotically, as there are \$n!\$ results. And we must generate each one.
