You can often use a stack or queue to avoid recursion. Implement this algorithm for computing all permutations of a string str without recursion.

  1. Add "|" + str to the queue.
  2. While the queue is not empty,
    • Remove the element at the front. It has the form s | t. (That is, s is the substring before the | and t is the substring after the |.)
    • For each letter c in t, add s + c + "|" + (t with c removed) to the queue
    • However, if the | is at the end (that is, t is empty), add s to the result.

Using this algorithm, implement a method

public static ArrayList<String> permutations(String s)

Draft: Your program should work for a string of length ≤ 2.