// generate the permutations of a string

public class PermuteString {
   private String word;
   private int index;
   private PermuteString substringGenerator;

    // PermuteString: default constructor
    public PermuteString(String s) {
      word = s;
      index = 0;
      if (s.length() > 1)
         substringGenerator = new PermuteString(s.substring(1));
   }

    // nextPermutation: return next permutation of word
    public String nextPermutation() {
      if (word.length() == 1) {
         ++index;
         return word;
      }
      else {
         String r = word.charAt(index)
          + substringGenerator.nextPermutation();
         if (!substringGenerator.morePermutations()) {
            ++index;
            if (index < word.length()) {
               String tailString = word.substring(0, index)
                + word.substring(index + 1);
               substringGenerator = new PermuteString(tailString);
            }
         }
         return r;
      }
   }

   // morePermutations: return true of more permutations available
   public boolean morePermutations() {
      return index < word.length();
   }
}